题目描述

译自 COI 2010 T4. ROBOTI

这是一道交互题。

两个机器人被困在一个仓库中，两个机器人被编号为 $1$ 和 $2$。这个仓库是一个 $R$ 行 $C$ 列的网格，每个单元格要么是空的，要么是被占用的。机器人用无线电命令控制。每个命令包含两部分数据：

• robot：值为 $1$ 或 $2$，表示我们要移动的机器人编号；
• direction：值为字母 U，D，L 或 R，表示我们希望机器人向哪个方向移动（上下左右，每次移动一格）。

如果目的单元格被占用，被另一个机器人占用或者在仓库外面，机器人会停留在原地，什么事都不会发生，否则机器人就会移向目的单元格。

机器人装配有 GPS 系统，然而由于部署时出现了故障，我们不能知道机器人的确切位置，只能知道两个机器人之间的曼哈顿距离。如果两个机器人分别位于 $(r_1,c_1)$ 和 $(r_2,c_2)$，那么它们之间的曼哈顿距离为 $|r_1-r_2|+|c_1-c_2|$。

在每次操作后，无论成功与否，我们唯一能知道的信息只是两个机器人之间的曼哈顿距离。

机器人目前位于两个不同且没有被占用的单元格中。写一个程序将两个机器人分别移动到给定点处。保证仓库中所有未被占用的单元格都是连通的。

输入格式

在交互前你需要从标准输入获取以下信息：

第一行两个整数 $r,c$，表示仓库的规模；

接下来 $r$ 行，每行 $c$ 个字符，描述这个仓库。字符只包含 .，# 和 x。. 表示未被占用的单元格，# 表示被占用的单元格，x 表示机器人的目的地。保证有且仅有两个 x 字符。

最后会给出初始状态下两机器人之间的曼哈顿距离。

你需要通过标准输入输出与交互器进行交互。对于每一条命令，输出一个整数和一个字符并用一个空格隔开，分别表示要控制的机器人和机器人移动的方向，值域同题目描述。输出命令结束后，你需要刷新标准输出，利用 fflush(stdout) 命令或对应命令。

如果命令结束，则输出一个 0 后退出程序。

样例

利用附加文件中的 grader.cpp 测试时，输入如下：

第一行两个整数 $r,c$，表示仓库的规模；

接下来 $r$ 行，每行 $c$ 个字符，表示目前状态。字符包括 .，#，1，2 和 x。其中除数字之外的字符意义同输入，数字表示对应机器人的初始位置。

在测评时，交互器将把数字转化为 .。

样例输入

4 5
##x1.
.##..
.....
2...x

数据范围与提示

对于 $40$ 分的数据，不包含被占用的单元格；

对于 $80$ 分的数据，$R,C\le 50$；

对于全部数据，$2\le R,C\le 200$。

交互器使用方法

测试程序时，需将输入保存在一个文件中，利用如下命令编译交互器：

g++ grader.cpp -o grader -O2 -std=c++11

并利用如下命令运行（Linux）：

./grader <file_name>

或（Windows）：

grader <file_name>

其中，file_name 指输入文件的名称。

你可以运行两个终端来进行程序测试。