题目描述

我们考虑主机游戏 Sonic 3 & Knuckles 的奖励关卡的一个简化版本。

Sonic 在一个 $N\times M$ 的网格中移动。每一步，他可以向右、向左、向上或向下移动一格，但不能走出网格。

Sonic 不能做 $180^\circ$ 掉头：如果他刚向左移动了一格，那么下一步不能向右移动；反之亦然。同样，向上走之后不能立刻向下走，向下走之后不能立刻向上走。

每个格子上可能有以下对象之一：

• 白球：Sonic 不能进入该格子。
• 红球：Sonic 不能进入该格子。
• 蓝球：如果 Sonic 进入该格子并随后离开，那么该蓝球会变成红球。

此外，还有一条额外规则：如果在某一时刻，网格中出现了一个由蓝球组成的、按边相连的、没有洞的连通块，并且这个连通块至少包含一个蓝球，而且从每个方向看都被紧邻的红球和/或白球包围（包括斜角方向），那么该连通块中的所有蓝球都会消失；同时，该连通块所有紧邻的红色邻居也会消失（包括斜角相邻的红球），但白色邻居不会消失。

这个检查发生在 Sonic 离开某个格子之后、到达下一个格子之前；也就是说，如果他刚离开的格子上原本有蓝球，该球可能已经变成红球，然后再进行上述检查。如果同时出现多个满足条件的连通块，那么所有球的移除会同时发生。

一旦网格中所有蓝球都消失，所有其他球也会立即从网格中消失，游戏获胜。

你的任务是找出一串移动，使游戏获胜。

下面给出若干移动示例以帮助理解。Sonic 的位置用黑点表示。行从上到下编号为 $1$ 开始，列从左到右编号为 $1$ 开始。例如，$(3,4)$ 表示第 $3$ 行第 $4$ 列的格子。

首先，Sonic 向右走三步。每次 Sonic 离开带蓝球的格子时，该蓝球都会变成红球。第三步之后，Sonic 到达 $(1,4)$，该格子上有蓝球。随后他向下走。Sonic 一离开该格子，该蓝球就变成红球。此时网格中已经没有蓝球，因此游戏获胜，其他所有球也都会消失。所以当 Sonic 到达 $(2,4)$ 时，该格子已经是空格。

原题中的第一个状态序列图：展示 Sonic 从第一行连续向右移动，再向下移动，最终消除所有蓝球的过程。

初始时，Sonic 位于 $(3,2)$，该格子上有蓝球。他向下走，$(3,2)$ 上的球变成红球。尽管 $(3,4)$、$(4,2)$、$(4,3)$、$(4,4)$、$(5,2)$、$(5,3)$、$(5,4)$ 上的球组成了一个按边相连的蓝球连通块，但此时还不会有球消失，因为该连通块并没有在所有方向上都被红球或白球包围：$(4,2)$ 有一个斜角邻居 $(3,1)$，该格子为空。

之后 Sonic 向右走，$(4,2)$ 上的球变成红球。现在一些蓝球组成了一个按边相连的连通块，并且该连通块被红球和白球包围。这个连通块中的所有球和它们紧邻的红色邻居都会消失。白球不会消失，例如 $(6,3)$ 上的白球仍会保留。同样，$(1,3)$ 上的红球也会保留，因为它不是该连通块中某个球的紧邻邻居。

然而游戏还没有获胜，因为 $(2,1)$ 上仍然有一个蓝球。

此处应插入原题中的第二个状态序列图：展示一个被虚线圈出的蓝球连通块被包围并消失的过程。

初始时，Sonic 位于 $(2,2)$，该格子上有蓝球。他向下走，$(2,2)$ 上的蓝球变成红球。由于 $(3,2)$ 和 $(2,3)$ 上的球不是按边相连的，所以它们不构成同一个连通块，而是分别构成各自的连通块。但是没有任何球会消失，因为 $(3,2)$ 并没有在所有方向上都被红球和白球包围：$(3,2)$ 有一个斜角相邻的格子 $(2,3)$，而那里不是红球或白球，而是蓝球。

【图片占位】此处应插入原题中的第三个状态序列图：展示两个蓝球斜角相邻但不属于同一个按边连通块，并因此不会触发消除。

说明示例四

初始时，Sonic 位于 $(1,3)$，该格子上有蓝球。他先向下走两次，$(1,3)$ 和 $(2,3)$ 上的球都变成红球。接着 Sonic 从 $(3,3)$ 向左走，$(3,3)$ 上的球变成红球。此时 $(2,2)$ 上的蓝球组成了一个被红球包围的连通块；同时，$(2,4)$ 上的蓝球也组成了一个被红球包围的连通块。这两个蓝球以及包围它们的所有红球会被同时移除。

展示两个蓝球连通块同时满足消除条件并同时被移除的过程。

评分方式

本题通过测试系统给出了 $10$ 个输入文件：input_000.txt 到 input_009.txt。作为解答，需要提交对应的输出文件：output_000.txt 到 output_009.txt。

不需要提交程序，程序也不会被评测。每个输入文件中都有一些特殊性质的网格，因此建议分别分析每个输入文件。

测试系统还提供了评测程序 checker.cpp，用于检查解答。使用它时，需要在编译时把它和辅助文件 testlib.h 放在同一目录下。testlib.h 也可在测试系统中获得。

输入格式

输入文件第一行包含两个整数 $N$ 和 $M$，分别表示网格的行数和列数。

$$1\le N,M\le 400$$

接下来 $N$ 行，每行是一个长度为 $M$ 的字符串。字符串中的每个字符为以下之一：

• .：空格子；
• S：Sonic 的起点；
• #：白球；
• x：红球；
• o：蓝球。

Sonic 的起点是空格。字符 S 在网格中恰好出现一次。

输出格式

输出文件中写入一个字符串，描述 Sonic 的路径。

该字符串只能由字符 L、R、U、D 组成，分别表示向左、向右、向上、向下移动一格。

字符串长度不得超过 $10^6$。

注意：不需要最小化步数。

样例 1

输入

2 5
Sooox
...x.

输出

RRRD

样例 2

输入

6 5
..x..
oSxx#
.oxox
xooox
xooo#
xx#x#

输出

DDRULULU

样例 3

输入

5 5
..S..
xxoxx
xooox
xxoxx
.o...

输出

DDDLDR

样例说明

前两个样例分别对应题面中说明示例一和说明示例二。第三个样例是题面中说明示例四的扩展版本。

下发文件