问题文

在一个 $N × N$ 的网格中，有 $M$ 台机器人，$B$ 个障碍物格子和一个目标格子。

每个格子都有坐标，左上角的格子坐标是 $(0, 0)$，右上角的格子坐标是 $(0, N - 1)$，右下角的格子坐标是 $(N - 1, N - 1)$。该网格的左边和右边、上边和下边相连，例如格子 $(3, 0)$ 的左边的格子是 $(3, N - 1)$，格子 $(N - 1, 5)$ 的正下方的格子是 $(0, 5)$。

为每个机器人 $i$ ($1 \leq i \leq M$)，给出初始位置 $(ry_i, rx_i)$ 和初始朝向 $c_i$。$c_i$ 是 U, D, L, R 中的一个，分别代表上、下、左、右。

此外，还给出了每个障碍物格子和目标格子的坐标。第 $i$ 个障碍物格子 ($1 \leq i \leq B$) 的坐标是 $(by_i, bx_i)$，目标格子的坐标是 $(gy, gx)$。

您可以选择若干个格子并在其上放置 方向指示器。每个方向指示器指定向上、向下、向左或向右其中之一的方向。不能在一个格子上放置多个方向指示器。

在放置了方向指示器后，每个机器人都会独立地执行以下动作。机器人之间不会发生碰撞。

• 如果机器人处于目标格子上：停止。
• 否则：首先，如果当前所处的格子上有方向指示器，则按照指示器指定的方向改变自己的朝向。然后，向自己面朝的方向移动一格（注意网格的左边和右边、上边和下边相连）。但是，如果移动目标是一个障碍物格子，则移动失败，停止在原地。

请尽量使能够有限次动作到达目标格子的机器人的数量尽可能多。使用的方向指示器越少，机器人经过的格子越多，得分越高。请参阅“输出”部分以获取更详细的信息。

【注意】本问题中无需求解“最优解”。例如，无需将所有机器人都带到目标格子上，也无需最小化方向指示器的数量。

限制条件

• $N = 40$
• $M = 100$
• $B = 300$
• $0 \leq gy, gx \leq N - 1$
• $0 \leq ry_i, rx_i \leq N - 1$
• $c_i$ 是 U, D, L, R 中的一个。
• $0 \leq by_i, bx_i \leq N - 1$
• 障碍物格子不与机器人、目标格子或其他障碍物格子重叠。（机器人之间或机器人与目标格子可能重叠）
• 在满足以上限制条件的情况下，障碍物格子、目标格子和机器人所在的格子是均匀随机选择的。

输入

输入以以下格式给出：

$N$ $M$ $B$ $gy$ $gx$ $ry_1$ $rx_1$ $c_1$ $ry_2$ $rx_2$ $c_2$ $:$ $ry_M$ $rx_M$ $c_M$ $by_1$ $bx_1$ $by_2$ $bx_2$ $:$ $by_B$ $bx_B$

输出

以以下格式输出：设指示器的数量为 $K$，第 $i$ 个指示器的放置坐标为 $(Y_i, X_i)$，第 $i$ 个指示器指定的方向为 $R_i$（是 U, D, L, R 中的一个，分别代表上、下、左、右）。

$K$ $Y_{1}$ $X_{1}$ $R_1$ $Y_{2}$ $X_{2}$ $R_2$ $:$ $Y_{K}$ $X_{K}$ $R_K$

如果不满足上述格式，则输出为「不正确」。例如，字符串数量不匹配或使用了未指定的字符。

另外，如果在同一个格子上放置了多个方向指示器，也视为不正确。但是，在目标格子或障碍物格子上放置方向指示器不算不正确。

提供了50个测试用例。对于每个测试用例，设能够通过有限次动作到达目标格子的机器人数量为 $A$，放置的方向指示器数量为 $B$，机器人经过的格子数量为 $C$，那么该测试用例的得分为 $1000 \times A - 10 \times B + C$。 提交的得分将是所有测试用例得分的总和。

如果输出不正确，则与输入示例中的测试用例相应的得分为 $0$。否则，除输入示例之外的所有测试用例的得分均为 $0$。

示例

可以从此链接下载输入和输出示例。