227 - Puzzle

有一種拼圖以 5x5 大小的方格所構成，其中包含24個相同大小的小方塊，小方塊上分別印有一個英文字母。由於只有24個小方塊，所以會有一個位置是空的，在空格四週的方塊可以移到空格中。請參考下圖。

左圖經過六次的移動可變為右圖的形式，步驟如下：

1. 空格上方的方塊D向下移動。
2. 空格右方的方塊O向左移動。
3. 空格右方的方塊K向左移動。
4. 空格下方的方塊L向上移動。
5. 空格下方的方塊B向上移動。
6. 空格左方的方塊A向右移動。
   

給定方格一開始的佈局及移動步驟，請輸出方格最後的形式。

Input

輸入會有多組測試資料，每組資料的前五列每列有五個字元，表示方格一開始的佈局，以空白字元表示空格。第六列開始為移動步驟，每個步驟一個字元，以A表示空格上面的方塊向下移動；B表示空格下面的方塊向上移動；R表示空格右邊的方塊向左移動；L表示空格左邊的方塊向右移動。注意可能會有不合法的移動方式(就算所有移步僅包含ABRL，也可能會有不合法的移步)，若出現不合法的移步，則視為該組資料無解。移步可能會有許多列，並以 0 表示移步結束。當出現字元 Z 表示測試資料結束。

Output

請在每組測試資料輸出資料編號(Puzzle #1, Puzzle #2...)，若無解請輸出"This puzzle has no final configuration."，否則請輸出方塊最後的佈局，每列的字母以一個空白字元隔開，請參考範列輸出。

請每組輸出之間以一列空行隔開。

Sample Input

TRGSJ
XDOKI
M VLN
WPABE
UQHCF
ARRBBL0
ABCDE
FGHIJ
KLMNO
PQRS 
TUVWX
AAA
LLLL0
ABCDE
FGHIJ
KLMNO
PQRS 
TUVWX
AAAAABBRRRLL0
Z

Sample Output

Puzzle #1:
T R G S J
X O K L I
M D V B N
W P   A E
U Q H C F

Puzzle #2:
  A B C D
F G H I E
K L M N J
P Q R S O
T U V W X

Puzzle #3:
This puzzle has no final configuration.

原文出處