AT_abc453_d [ABC453D] Go Straight

有一个由 $H$ 行 $\times$ $W$ 列组成的网格。高桥在网格中上下左右移动。 从上往下第 $i$ 行，从左往右第 $j$ 列 $(1\leq i\leq H, 1\leq j\leq W)$ 的单元格的状态用字符 $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`：此格是高桥的目的地。此格可以自由进出。 刚好有一个 $(i,j)$ $(1\leq i\leq H, 1\leq j\leq W)$ 满足 $S_{i,j}=$ `S`，刚好有一个 $(i,j)$ $(1\leq i\leq H, 1\leq j\leq W)$ 满足 $S_{i,j}=$ `G`。 高桥想要通过重复地从起始位置向上、下、左或右移动到相邻的单元格来到达目的地。 请判断这是否可行，如果可行，请输出一个在相邻单元格之间最多有 $5\times 10^6$ 次移动的有效移动序列。 可以证明，如果在问题的条件下存在一个有效的移动序列，那么就存在一个最多有 $5\times 10^6$ 次移动的序列。 只要移动次数最多为 $5\times 10^6$ ，就没有必要最小化移动次数。

输入内容由标准输入法提供，格式如下 >$H$ $W$ $S_{1,1} S_{1,2} \ldots S_{1,W}$ $S_{2,1} S_{2,2} \ldots S_{2,W}$ $\vdots$ $S_{H,1} S_{H,2} \ldots S_{H,W}$

如果无法在满足条件的情况下到达目的地，则在第一行输出 `No`，在第二行不输出任何内容。 如果可以在满足条件的情况下到达目的地，则在第一行输出 `Yes`。 在第二行中，输出一个字符串 $T$ 代表一连串的移动。 $T$ 必须满足以下所有条件。 - $T$ 的长度 $\lvert T\rvert$ 介于 $1$ 和 $5\times 10^6$ 之间（包括首尾）。 - $T$ 中的每个字符都是 `U`、`D`、`L`、`R` 中的一个。 - $T$ 的第 $i$ 个字符是 `U`、`D`、`L`、`R`，这意味着在出发后的第 $i$ 次移动中，高桥分别移动到相邻单元格的上方、下方、左侧或右侧。 - 对于 $1\leq i\leq \lvert T\rvert$ ，高桥在第 $i$ 步之后不在网格之外。 - 在移动过程中，每个单元格的条件都没有被违反。 - 在第 $\lvert T\rvert$ 次移动之后，高桥位于目的地单元格。只要满足这个条件，他就可以在 $\lvert T\rvert$ 步之前通过目的单元格。

#### 样例解释 #1 让单元格 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的单元格。 根据样例输出，路径为：$(2,2)$ $\to$ $(3,2)$ $\to$ $(3,3)$ $\to$ $(3,2)$ $\to$ $(2,3)$ $\to$ $(1,3)$ $\to$ $(2,3)$ $\to$ $(3,3)$ $\to$ $(3,4)$ $\to$ $(3,5)$，到达目的地。 其他解决方案，如 `DRUURLRRDD` 也被接受。另一方面，由于高桥无法直接穿过 $(3,3)$ 单元格，因此 `DRRR` 等解法不被接受。 #### 样例解释 #3 不可能在满足条件的情况下到达目的地。 #### 限制因素 - $1 \leq H,W\leq 1000$ - $S_{i,j}$ 是 `#`, `.`, `o`, `x`, `S`, `G` 中的一个 - 正好有一个 $(i,j)$ 满足 $S_{i,j}=$ `S`，正好有一个满足 $S_{i,j}=$ `G` - $H$ 和 $W$ 是整数