AT_masters2025_qual_a Ore Rolling (A)

有一个用 $N \times N$ 的格子表示的洞窟。最左上角的格子的坐标为 $(0,0)$，从这里向下走 $i$ 格、向右走 $j$ 格后的位置坐标为 $(i,j)$。洞窟的四周被墙壁包围，无法走出洞窟。 洞窟内散落着岩石和 $M$ 种矿石。此外，洞窟内的 $M$ 个不同的格子上各有一个洞，第 $i$ 种矿石需要全部投入第 $i$ 个洞中。**岩石可以投入任意洞，也可以留在洞窟内不处理。**你最多可以进行 $10000$ 次如下操作： 1. 向上下左右相邻的格子移动。**即使目标格子上有洞、岩石或矿石也可以移动。** 2. 将当前位置的岩石或矿石搬运到上下左右相邻的格子。**目标格子不能已有其他岩石或矿石。目标格子可以是洞。**如果搬运到洞，岩石或矿石会掉入洞中并被移除。你的当前位置会变为搬运目标格子。 3. 将当前位置的岩石或矿石向上下左右某个方向滚动。被滚动的岩石或矿石会沿直线滚动，直到遇到岩石、矿石、墙壁而停止，或掉入洞中。你的当前位置不会改变。 滚动操作的详细规则如下： 1. 如果滚动方向相邻的格子是洞，岩石或矿石会掉入洞中并被移除。 2. 如果滚动方向相邻的格子有岩石、矿石，或超出 $N \times N$ 的范围，则在当前位置停止。 3. 若以上两种情况都不满足，则移动到相邻格子并重复处理。 滚动速度极快，因此在你下一步行动前，岩石或矿石必定已经停止或掉入洞中。 请你用尽量少的操作次数，将所有矿石投入对应的洞中。

输入通过标准输入给出，格式如下： > $N$ $M$ > $C_0$ > $\vdots$ > $C_{N-1}$ - 棋盘大小 $N$ 在所有测试用例中均为 $N=20$。 - 矿石种类数 $M$，每个问题固定，详见“输入生成方法”部分。 - 对于每个 $i=0,1,\dots,N-1$，$C_i$ 是长度为 $N$ 的字符串，第 $j$ 个字符表示格子 $(i,j)$ 的初始状态： - `@`：有岩石。 - `a`-`z`：有矿石。 - `A`-`Z`：有洞。 - `.`：什么都没有。 矿石和洞由大小写字母一一对应。例如，字母 `a` 表示的矿石应投入字母 `A` 表示的洞。只使用前 $M$ 个英文字母，同种矿石可能有多个，但同种洞只会有一个。 你初始时位于洞 `A` 所在的格子。

第 $t$ 步的操作用操作类型编号 $a_t \in \{1,2,3\}$（1:移动，2:搬运，3:滚动）和方向字符 $d_t \in \{U,D,L,R\}$ 的对 $(a_t, d_t)$ 表示。例如，$(3, R)$ 表示将当前位置的岩石或矿石向右滚动。 请按如下格式输出： > $a_0$ $d_0$ > $\vdots$ > $a_{T-1}$ $d_{T-1}$

### 得分 设输出的操作序列长度为 $T\ (\leq 10000)$，初始棋盘上的矿石总数为 $K$，成功投入正确洞的矿石数为 $A$，则得分如下： - 若 $A=K$，得分为 $\mathrm{round}(10^6\times(1+\log_2{\frac{10000}{T}}))$。 - 若 $A