HZNUOJ

与小明一起操纵小车

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:70     AC:26     Score:99.24

Description

小明参加了电子设计竞赛,需要控制小车跨越一片障碍,但是缺少控制小车的指令,现在请求你的帮助。

障碍为一个n*m的矩阵,每个元素可能为"_","#","S","T"。

"_"表示空地,小车可以通过。

"#"表示墙壁,小车不能通过。

"S"和"T"分别为小车的起始点和需要到达的终点

矩阵一共n行,n为奇数,其中奇数行除了"S"和"T"一定全为"_"。

所有偶数行仅存在一个"_"

指令是一个字符串,字符串中仅包含"U","D","L","R"

矩阵左上角为(1,1),右下角为(n, m)

"U"可以使小车从(i,j)运动到(i - 1,  j)

"D"可以使小车从(i,j)运动到(i + 1,j)

"L"可以使小车从(i,j)运动到(i,j - 1)

"R"可以使小车从(i,j)运动到(i,j + 1)

现在请你输出一行指令集,使小车从S运动到T。

Input

输入为单组。

第一行输入n和m表示障碍为一个n*m的矩阵(1≤n,m≤100

接下来输入n行,每行表示障碍的状态。

Output

输出一行表示使小车运动的指令

Samples

input
3 5 __T__ ####_ _S___
output
RRRUULL

Author

CHEN, Zequn