Програмчлал, Алгоритмд дуртай бүхэнд зориулав

Өндөр H, өргөн W талбар өгөгдөв. Энэ талбарт байгаа модон хашааг ' * ', хоосон талбайг ' . ', төмөр хашааг ' # ' , усыг ' - ', танкны чиглэл дээш '^', доош ' v ', баруун ' > ', зүүн ' < ' гэж тус тус тэмдэглэв. Энэ талбарт ганц танк байх бөгөөд танкны хувьд дараах үйлдэл өгөгдөв. ' S ' буудах: Сум нь талбайгаас гартал эсвэл хашаа тултал явах бөгөөд модон хашаа бол сөнөөж хоосон талбар үүснэ. ' R ' баруун, ' L ' зүүн, ' U ' дээш, ' D ' доош гэсэн чиглэл уруу танк эргээд дараах нүд нь хоосон бол тийш шилжинэ. Хэсэг үйлдэлийн дараа талбар ямар байдалтай болохыг бодож ол.

Оролт

Эхний мөр тестийн тоо Т
Тест болгон дараа хэлбэртэй байна
H W:  1< H, W <21 
Талбарыг төлөөлөх тэмдэгтүүд
N: үйлдэлийн тоо 0< N <101
Үйлдүүд

Example

Input

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

Output

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

ˆ-#**
.-.#*
.-..#

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