You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道交互题。

镜像迷宫是一个矩形网格，其边界以及部分内部实心矩形区域被镜面格子占据。边界与镜面矩形、两个镜面矩形之间至少被一行或一列隔开。形式化地，若 $(x_1,y_1)$ 与 $(x_2,y_2)$ 都是镜面格，且$\max(\lvert x_1-x_2\rvert,\lvert y_1-y_2\rvert)\le 1$，则它们要么都是边界，要么属于同一个镜面矩形。

当沿某个方向进入镜面格子后，会出现在对侧镜面格子之外的空格。形式化地，若 $(x,y)$ 为空格，$(x,y+1)$ 为镜面格，从 $(x,y)$ 出发沿 $(0,1)$ 方向走一步，会到达坐标为 $(x,z)$ 的空格，满足：$z\le y$ 且 $(x,z-1)$ 为镜面格且对于任意 $z\le w\le y$，$(x,w)$ 都是空格。其他方向同理。

如图所示为一个 9 行 12 列的镜面迷宫，黑色区域为镜面。1 号格子向上走一步到达上边界镜面，随即被反射至下方的 2 号格子，同理 2 号格子向下走一步会到达 1 号格子。3 号格子向上走一步到达 4 号格子，5 号格子向左走一步到达 6 号格子。7 号格子向上或向下走一步都仍在 7 号格子。

初始时，旅行家位于迷宫左下角的空格（即上图的 4 号格子）。为了确定迷宫的地形，旅行家会对迷宫进行探索，并标记经过的空格。旅行家将初始位置标记为 0。对于每次探索，旅行家会首先回到之前标记过的某个空格，然后向某个方向走一步，如果她到达了一个未标记过的空格，就会将其标记为一个新的编号。

探索是具有危险性的，因此旅行家希望将总探索次数控制在一定范围之内，你能帮助她吗？

交互方式

旅行家可以进行多次探索，每次探索需要向标准输出输出一行，包含一个大写字母和一个非负整数 $p$，用空格隔开。大写字母为 U/D/L/R 之一，分别表示以 $p$ 为起点，向上/下/左/右走一步。$p$ 必须是已知的空格编号（编号为0的位置固定位于左下角的空格，初始时即已知）。

每次探索后，从标准输入中读取结果，结果为一行，包含一个 $0\sim 10^6$ 之间的整数，表示到达的空格编号 $q$。如果探索到了一个新的空格，$q$ 会被指定为一个新的编号，保证编号不会重复。无论是否探索结果是新空格还是已知的空格，均计入总探索次数。

每次探索后，旅行家可以选择汇报迷宫的完整地形并结束探索过程（即使此时迷宫中仍有未探索过的空格）：首先向标准输出输出一行，格式为! n m，表示迷宫有 $n$ 行 $m$ 列。之后向标准输出输出 $n$ 行，每行包含 $m$ 个字符，字符为.或*之一，分别表示空格与镜面格。输出结束后，程序应立即退出。

总探索次数不得超过 $(n-2)(m-2)+1$。数据保证 $n\ge 3,m\ge 3$ 且 $nm\le 10^4$。

注意：初始时，迷宫尺寸对于旅行家也是未知的。

任何不符合交互要求的输出，包括交互格式错误、探索次数超出限制等，都会导致未定义的运行结果。

样例 #1

样例输入 #1

260522

914575

436426

436426

979445

979445

样例输出 #1

D 0

L 260522

U 914575

L 0

U 436426

R 979445

! 9 12
************
*..........*
*.***......*
*.***...*..*
*.***...*..*
*..........*
*.********.*
*..........*
************

提示

样例展示了一个可能的交互过程，根据地图的尺寸，探索次数不得超过71次，实际探索次数为6次，符合要求。