AT_arc103_b.[ABC111D] Robot Arms

在すぬけ君的工厂里，计划引进一种具有以下特性的机器人手臂：

• 机器人手臂由 $m$ 个手臂和 $m+1$ 个关节组成。手臂编号为 $1, 2, ..., m$，关节编号为 $0, 1, ..., m$。手臂 $i$ 连接关节 $i-1$ 和关节 $i$。手臂 $i$ 的长度为 $d_i$。
• 每个手臂都可以独立指定模式。模式可以是 L、R、D、U 中的任意一个，手臂的模式决定了该手臂的方向。将工厂视为坐标平面时，关节 $i$ 的坐标 $(x_i, y_i)$ 按如下方式确定：
  • $ (x_0, y_0) = (0, 0) $。
  • 当手臂 $i$ 的模式为 L 时，$ (x_i, y_i) = (x_{i-1} - d_i, y_{i-1}) $。
  • 当手臂 $i$ 的模式为 R 时，$ (x_i, y_i) = (x_{i-1} + d_i, y_{i-1}) $。
  • 当手臂 $i$ 的模式为 D 时，$ (x_i, y_i) = (x_{i-1}, y_{i-1} - d_i) $。
  • 当手臂 $i$ 的模式为 U 时，$ (x_i, y_i) = (x_{i-1}, y_{i-1} + d_i) $。

すぬけ君希望通过巧妙地指定手臂的模式，使得机器人手臂的关节 $m$ 能恰好到达 $N$ 个点 $(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)$ 中的任意一个。请判断是否存在这样的机器人手臂。如果存在，请给出满足条件的机器人手臂，以及对于每个点 $(X_j, Y_j)$，使机器人手臂的关节 $m$ 到达该点的模式指定方法。

输入按以下格式从标准输入读入。

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

如果存在满足条件的方案，请按以下格式输出。如果不存在，输出 -1。

$m$
$d_1$ $d_2$ $\ldots$ $d_m$
$w_1$
$w_2$
$\vdots$
$w_N$

其中，$m$ 和 $d_i$ 表示机器人手臂的信息，具体含义见题目描述。要求 $1 \leq m \leq 40$，$1 \leq d_i \leq 10^{12}$，且 $m, d_i$ 均为整数。

$w_j$ 是长度为 $m$ 的字符串，表示使机器人手臂的关节 $m$ 到达点 $(X_j, Y_j)$ 的模式指定方法。$w_j$ 的第 $i$ 个字符为 L、R、D、U 中的一个，表示手臂 $i$ 的模式。

限制条件

• 输入均为整数。
• $1 \leq N \leq 1000$
• $-10^9 \leq X_i \leq 10^9$
• $-10^9 \leq Y_i \leq 10^9$

部分得分

• 对于 $300$ 分的测试点，有 $-10 \leq X_i \leq 10$ 且 $-10 \leq Y_i \leq 10$。

样例解释 1

对于每个 $(X_j, Y_j)$，使机器人手臂的关节 $m$ 到达该点的方法如下：

• 对于 $(X_1, Y_1) = (-1, 0)$，首先关节 $0$ 的位置为 $(x_0, y_0) = (0, 0)$。手臂 $1$ 的模式为 R，所以关节 $1$ 的位置为 $(x_1, y_1) = (1, 0)$。手臂 $2$ 的模式为 L，所以关节 $m=2$ 的位置为 $(x_2, y_2) = (-1, 0)$。
• 对于 $(X_2, Y_2) = (0, 3)$，$(x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3)$。
• 对于 $(X_3, Y_3) = (2, -1)$，$(x_0, y_0) = (0, 0), (x_1, y_1) = (0, -1), (x_2, y_2) = (2, -1)$。

样例解释 3

$(X_j, Y_j)$ 中可能包含相同的点。

由 ChatGPT 4.1 翻译