题目描述

有一个 $H$ 行 $\times$ $W$ 列的网格，高桥在此网格中进行上下左右的移动。第 $i$ 行（从上往下）第 $j$ 列（从左往右）的单元格状态由字符 $S_{i,j}$ 表示，$S_{i,j}$ 是 #、.、o、x、S、G 中的一种。

• $S_{i,j} =$ #：此单元格不可进入。
• $S_{i,j} =$ .：此单元格可自由进出。进入后可向上下左右任意相邻格移动。
• $S_{i,j} =$ o：在此单元格中，高桥必须沿与上一步相同的方向移动。进入后必须不改变方向地移动到下一格。
• $S_{i,j} =$ x：在此单元格中，高桥不能沿与上一步相同的方向移动。进入后必须改变方向。掉头 180 度也视为改变方向。
• $S_{i,j} =$ S：起始位置，可自由进出。
• $S_{i,j} =$ G：目的地，可自由进出。

保证 S 和 G 各恰好出现一次。

判断高桥能否从起点出发到达目的地。若能，输出一个移动次数不超过 $5 \times 10^6$ 的合法移动序列（不要求最短）。

输入格式

H W
S_{1,1}S_{1,2}...S_{1,W}
...
S_{H,1}S_{H,2}...S_{H,W}

输出格式

若无法到达，输出 No。

若可以到达，第一行输出 Yes，第二行输出移动序列字符串 $T$。$T$ 的每个字符为 U（上）、D（下）、L（左）、R（右）之一。

输入示例 1

3 5
.#...
.Sooo
..x.G

输出示例 1

Yes
DRUUDDRR

示例 1 说明

按示例输出行走的路径为：$(2,2) \to (3,2) \to (3,3) \to (2,3) \to (1,3) \to (2,3) \to (3,3) \to (3,4) \to (3,5)$，到达目的地。DRUURLRRDD 等也是正确答案。注意 $(3,3)$ 是 x 格，不能直行，因此 DRRR 不是正确答案。

输入示例 2

3 3
#So
xoG
..#

输出示例 2

Yes
DDLURR

输入示例 3

2 2
So
oG

输出示例 3

No

约束条件

• $1 \leq H, W \leq 1000$
• $S_{i,j}$ 是 #、.、o、x、S、G 中的一种
• 恰好有一个 S 和一个 G
• $H$、$W$ 均为整数