题目描述

王老板正在给他的工厂引进一种机械臂。这种机械臂由 $m$ 个零件和 $m + 1$ 个连接件构成，零件编号 $1 \sim m$，连接件编号 $0 \sim 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$ 个位置，请你帮王老板判断一下是否能够实现？如果可以实现，请你找出一种满足条件的机械臂连接方法。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行两个整数 $X_i, Y_i$，表示工厂中的坐标点。

输出格式

第一行一个整数 $m\ (1 \le m \le 40)$，表示机械臂的零件数。

第二行 $m$ 个整数 $d_i\ (1 \le d_i \le 10^{12})$，表示机械臂的第 $i$ 个零件的长度。

接下来 $N$ 行，每行一个长度为 $m$ 的字符串 $w_j$，表示将机械臂从点 $(X_{j-1}, Y_{j-1})$ 连接到点 $(X_j, Y_j)$ 的方法。

如果不能实现王老板的要求，输出一个 -1 即可。

3
-1 0
0 3
2 -1

2
1 2
RL
UU
DR

5
0 0
1 0
2 0
3 0
4 0

-1

2
1 1
1 1

2
1 1
RU
UR

3
-7 -3
7 3
-3 -7

5
3 1 4 1 5
LRDUL
RDULR
DULRD

提示

$50\%$ 的数据，$-10 \le X_i, Y_i \le 10$。

$100\%$ 的数据，$1 \le N \le 1000$，$-10^9 \le X_i, Y_i \le 10^9$。