机械臂

题目描述

Snuke 打算把具有以下性质的机械臂引入他的工厂:

机械臂由 $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)$

Snuke 希望通过适当指定各段的模式,使关节 $m$ 的位置能够与给定的所有 $N$ 个点 $(X_1, Y_1), (X_2, Y_2), ..., (X_N, Y_N)$ 匹配。这是否可能?

如果可能,请找出这样的机械臂构造,以及将关节 $m$ 移到每个点 $(X_j, Y_j)$ 的方式。

输入格式

输入按以下格式从标准输入给出:

$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$:$
$X_N$ $Y_N$

输出格式

如果条件可以满足,按以下格式输出。如果无法满足,输出 -1。

$m$
$d_1$ $d_2$ $...$ $d_m$
$w_1$
$w_2$
$:$
$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$ 的模式。

样例

3
-1 0
0 3
2 -1

2
1 2
RL
UU
DR

按照给出的方式把机械臂的关节 $m$ 移到各 $(X_j, Y_j)$ 时,各关节的位置如下:

• 到 $(X_1, Y_1) = (-1, 0)$:首先,关节 $0$ 的位置为 $(x_0, y_0) = (0, 0)$。由于段 $1$ 的模式为 R,关节 $1$ 的位置为 $(x_1, y_1) = (1, 0)$。接着,由于段 $2$ 的模式为 L,关节 $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)$

5
0 0
1 0
2 0
3 0
4 0

-1

2
1 1
1 1

2
1 1
RU
UR

点 $(X_j, Y_j)$ 中可能存在重复点。

3
-7 -3
7 3
-3 -7

5
3 1 4 1 5
LRDUL
RDULR
DULRD

数据范围

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