010 - バトルタウン

問題

あなたは友人たちとゲームを開発することにした． ゲームのタイトルは「バトルタウン」． 戦車による市街戦をテーマにしたゲームだ． ゲーム開発の第一歩として，次のようなプロトタイプを開発することにした．

このプロトタイプでは，登場する戦車はプレイヤーの戦車のみであり， 敵の戦車は登場しない． プレイヤーの戦車はプレイヤーの入力に従ってマップ上で様々な動作をする． 以下に，戦車の動作に関する仕様を述べる．

マップの構成要素は表1の通りである． 戦車が移動できるのはマップ内の平地の上だけである．

表1: マップの構成要素

文字	要素
.	平地
*	レンガの壁
#	鉄の壁
-	水
^	戦車（上向き）
v	戦車（下向き）
<	戦車（左向き）
>	戦車（右向き）

プレイヤーの入力は文字の列で与えられる． 各文字に対応する動作は表2の通りである．

表2: プレイヤーの入力に対する動作

文字	動作
U	Up: 戦車を上向きに方向転換し，さらに一つ上のマスが平地ならばそのマスに移動する
D	Down: 戦車を下向きに方向転換し，さらに一つ下のマスが平地ならばそのマスに移動する
L	Left: 戦車を左向きに方向転換し，さらに一つ左のマスが平地ならばそのマスに移動する
R	Right: 戦車を右向きに方向転換し，さらに一つ右のマスが平地ならばそのマスに移動する
S	Shoot: 戦車が現在向いている方向に砲弾を発射する

砲弾はレンガの壁あるいは鉄の壁にぶつかるか，マップの外に出るまで直進する． レンガの壁にぶつかった場合は，砲弾は消滅し，レンガの壁は平地に変化する． 鉄の壁にぶつかった場合は，砲弾は消滅するが，鉄の壁は変化しない． マップの外に出たときは砲弾はそのまま消滅する．

あなたの仕事は，初期マップとプレイヤーの入力操作列が与えられたときに， 最終的なマップの状態を出力するプログラムを作成することである．

入力

入力の1行目にはデータセット数を表す数 T (0 < T ≤ 100) が与えられる． この行に引き続き T 個のデータセットが与えられる．

各データセットの1行目にはマップの高さと幅を表す整数 H と W が 1つの空白文字で区切られて与えられる． これらの整数は 2 ≤ H ≤ 20, 2 ≤ W ≤ 20 を満たす． 続く H 行はマップの初期状態を表す． 各行は長さ W の文字列である． マップに含まれる文字はすべて表1で定義されたものであり， 全体でちょうど1つの戦車を含む． マップに続く行には入力操作列の長さ N (0 < N ≤ 100) が与えられ， 次の行には入力操作列を表す長さ N の文字列が与えられる． 入力操作列は表2で定義された文字のみからなる文字列である．

出力

各データセットに対し，すべての入力操作を終えた後のマップを， 入力マップと同じ形式で出力せよ． データセットの間には1行の空行を出力せよ． 最後のデータセットの後に余計な空行を出力しないよう注意すること．

入力例

4
4 6
*.*..*
*.....
..-...
^.*#..
10
SRSSRRUSSR
2 2
<.
..
12
DDSRRSUUSLLS
3 5
>-#**
.-*#*
.-**#
15
SSSDRSSSDRSSSUU
5 5
v****
*****
*****
*****
*****
44
SSSSDDRSDRSRDSULUURSSSSRRRRDSSSSDDLSDLSDLSSD

出力例

*....*
......
..-...
..>#..

<.
..

^-#**
.-.#*
.-..#

.....
.***.
..*..
..*..
....v