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 翻译