タイルを動かそう！

正方形のマス目を描いた枠付きの正方形の盤がある． 各マスは空か，英字を刻印したちょうどマスにはまるタイルがあるかのどちらかである． 盤を向こう側，手前側，左側，右側の 4 方向のいずれかに傾けると， すべてのタイルは盤の枠に押し詰められるまで上下左右に滑っていく．

下図に盤を手前に傾ける前後のタイルの配置の例を示す．

文字 U, D, L, R のそれぞれで，盤を向こう側，手前側，左側，右側に傾ける操作を表すことにしよう． さらに，これらの文字の列で操作の列を表すことにしよう． たとえば文字列 DRU は，盤をまず手前，次に右，最後に向こう側に傾ける一連の操作を表す．タイルは最初に下に，次いで右に，最後に上に動くことになる．

非常に長い操作列を扱うために操作列の繰り返しの表記を使うことにする． ある空ではない操作列 seq を k 回繰り返すことを (seq)k と記す． ここで k は整数である． 例えば (LR)3 は LRLRLR と同じ操作列を表す． 繰り返し表記はネストしていてもよい． 例えば ((URD)3L)2R は URDURDURDLURDURDURDLR を意味する．

タイルの初期位置と操作列が与えられたとき，その操作列に従って操作したあとのタイルの位置を計算するプログラムを書いてほしい．

Input

入力は 100 個以下のデータセットからなる． 各データセットは次の形式で表される．

n
s₁₁ ... s_1n
...
s_n1 ... s_nn
seq

最初の行の n は盤面の 1 行 (および 1 列) に並ぶマス目の数である (2 ≤ n ≤ 50)． 次の n 行は盤上の各マス目の初期状態を表す． s_ij は盤面の上から i 番目，左から j 番目のマス目 (どちらも1から数える) の初期状態を表す文字で，何も置いていないことを表す ‘.’ (ピリオド) であるか，タイルがあることとそこに刻印した文字を表す英大文字 ‘A’-‘Z’ のいずれかである．

seq は操作列を表す文字列である．seq の長さは 1 以上 1000 以下である． seq は上述の規則に従う操作列を表している． seq の中の繰り返し回数を表す数は 0 から始まらない 2 以上 10¹⁸ 以下の整数である． さらに，繰り返し表記をすべて展開した後の操作列の長さも 10¹⁸ 以下になると仮定してよい．

入力の終わりは，ゼロだけからなる行で表される．

Output

各データセットについて，初期状態から始めて指定された操作列に従って操作したあとの各マスの状態を出力せよ． 盤面の状態は入力で盤上のマスの初期状態を与えたのと同じフォーマットで n 行に出力せよ．

Sample Input

4
..E.
.AD.
B...
..C.
D
4
..E.
.AD.
B...
..C.
DR
3
...
.A.
BC.
((URD)3L)2R
5
...P.
PPPPP
PPP..
PPPPP
..P..
LRLR(LR)12RLLR
20
....................
....................
.III..CC..PPP...CC..
..I..C..C.P..P.C..C.
..I..C....P..P.C....
..I..C....PPP..C....
..I..C....P....C....
..I..C..C.P....C..C.
.III..CC..P.....CC..
....................
..XX...XX...X...XX..
.X..X.X..X..X..X..X.
....X.X..X..X..X..X.
...X..X..X..X..X..X.
...X..X..X..X...XXX.
..X...X..X..X.....X.
..X...X..X..X.....X.
.XXXX..XX...X...XX..
....................
....................
((LDRU)1000(DLUR)2000(RULD)3000(URDL)4000)123456789012
6
...NE.
MFJ..G
...E..
.FBN.K
....MN
RA.I..
((((((((((((((((((((((((URD)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L)2L
0

Output for the Sample Input

....
..E.
..D.
BAC.
....
...E
...D
.BAC
...
..C
.AB
....P
PPPPP
..PPP
PPPPP
....P
....................
....................
....................
....................
....................
XXXX................
PXXXX...............
CXXXX...............
XXXXX...............
XXPCXX..............
CCXXCX..............
CXXXXX..............
CXXXXX..............
CPCIXXX.............
CXPPCXX.............
PCXXXIC.............
CPPCCXI.............
CXCIPXXX............
XCPCICIXX...........
PIPPICIXII..........
......
......
N.....
JNG...
RMMKFE
BEAIFN

---