[ARC103B] Robot Arms

给定 $n$ 组坐标。构造长度为 $m$ 的序列 $\{c_n\}$ 和 $n$ 组包含 `LRUD` 的路径，满足对于每一组坐标： - $c_i$ 表示第 $i$ 步「步长」。 - 对于每个坐标，从 $(0,0)$ 开始走，共走 $m$ 步。第 $i$ 步可以让 $(x,y)$ 变成 $(x±c_i,y)$ 或 $(x,y±c_i)$ 。 - 走完 $m$ 次之后，恰好走到这组坐标。 - 要求 $m\leq 40,c_i\leq 10^{12}$ 。 $1\leq n\leq 1000$

[problemUrl]: https://abc111.contest.atcoder.jp/tasks/arc103_b すぬけ君の工場では，次のような特徴を持つ **ロボットアーム** を導入することになりました： - ロボットアームは， $ 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}) $ ． すぬけ君は，腕のモードをうまく指定することにより， $ N $ 個の点 $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ ...,\ (X_N,\ Y_N) $ のいずれにもロボットアームの関節 $ m $ をちょうど一致させられるようなロボットアームを導入したいです． このようなことは可能でしょうか？ 可能ならば，条件を満たすロボットアームおよび，各点 $ (X_j,\ Y_j) $ にそのロボットアームの関節 $ m $ を到達させるためのモードの指定方法を求めてください． Snuke is introducing a **robot arm** with the following properties to his factory: - The robot arm consists of $ m $ **sections** and $ m+1 $ **joints**. The sections are numbered $ 1 $ , $ 2 $ , ..., $ m $ , and the joints are numbered $ 0 $ , $ 1 $ , ..., $ m $ . Section $ i $ connects Joint $ i-1 $ and Joint $ i $ . The length of Section $ i $ is $ d_i $ . - For each section, its **mode** can be specified individually. There are four modes: `L`, `R`, `D` and `U`. The mode of a section decides the direction of that section. If we consider the factory as a coordinate plane, the position of Joint $ i $ will be determined as follows (we denote its coordinates as $ (x_i,\ y_i) $ ): - $ (x_0,\ y_0)\ =\ (0,\ 0) $ . - If the mode of Section $ i $ is `L`, $ (x_{i},\ y_{i})\ =\ (x_{i-1}\ -\ d_{i},\ y_{i-1}) $ . - If the mode of Section $ i $ is `R`, $ (x_{i},\ y_{i})\ =\ (x_{i-1}\ +\ d_{i},\ y_{i-1}) $ . - If the mode of Section $ i $ is `D`, $ (x_{i},\ y_{i})\ =\ (x_{i-1},\ y_{i-1}\ -\ d_{i}) $ . - If the mode of Section $ i $ is `U`, $ (x_{i},\ y_{i})\ =\ (x_{i-1},\ y_{i-1}\ +\ d_{i}) $ . Snuke would like to introduce a robot arm so that the position of Joint $ m $ can be matched with all of the $ N $ points $ (X_1,\ Y_1),\ (X_2,\ Y_2),\ ...,\ (X_N,\ Y_N) $ by properly specifying the modes of the sections. Is this possible? If so, find such a robot arm and how to bring Joint $ m $ to each point $ (X_j,\ Y_j) $ .

Input is given from Standard Input in the following format: ``` $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ : $ $ X_N $ $ Y_N $ ```

If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print `-1`. ``` $ m $ $ d_1 $ $ d_2 $ $ ... $ $ d_m $ $ w_1 $ $ w_2 $ $ : $ $ w_N $ ``` $ m $ and $ d_i $ are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, $ 1\ \leq\ m\ \leq\ 40 $ and $ 1\ \leq\ d_i\ \leq\ 10^{12} $ must hold. Also, $ m $ and $ d_i $ must all be integers. $ w_j $ is a string of length $ m $ that represents the way to bring Joint $ m $ of the robot arm to point $ (X_j,\ Y_j) $ . The $ i $ -th character of $ w_j $ should be one of the letters `L`, `R`, `D` and `U`, representing the mode of Section $ i $ .

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

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

### 制約 - 入力はすべて整数である - $ 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 $ が成り立つ． ### Constraints - All values in input are integers. - $ 1\ \leq\ N\ \leq\ 1000 $ - $ -10^9\ \leq\ X_i\ \leq\ 10^9 $ - $ -10^9\ \leq\ Y_i\ \leq\ 10^9 $ ### Partial Score - In the test cases worth $ 300 $ points, $ -10\ \leq\ X_i\ \leq\ 10 $ and $ -10\ \leq\ Y_i\ \leq\ 10 $ hold. ### Sample Explanation 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) $ です． ### Sample Explanation 3 $ (X_j,\ Y_j) $ の中に同じ点が含まれることもあります． ### Sample Explanation 5 In the given way to bring Joint $ m $ of the robot arm to each $ (X_j,\ Y_j) $ , the positions of the joints will be as follows: - To $ (X_1,\ Y_1)\ =\ (-1,\ 0) $ : First, the position of Joint $ 0 $ is $ (x_0,\ y_0)\ =\ (0,\ 0) $ . As the mode of Section $ 1 $ is `R`, the position of Joint $ 1 $ is $ (x_1,\ y_1)\ =\ (1,\ 0) $ . Then, as the mode of Section $ 2 $ is `L`, the position of Joint $ 2 $ is $ (x_2,\ y_2)\ =\ (-1,\ 0) $ . - To $ (X_2,\ Y_2)\ =\ (0,\ 3) $ : $ (x_0,\ y_0)\ =\ (0,\ 0),\ (x_1,\ y_1)\ =\ (0,\ 1),\ (x_2,\ y_2)\ =\ (0,\ 3) $ . - To $ (X_3,\ Y_3)\ =\ (2,\ -1) $ : $ (x_0,\ y_0)\ =\ (0,\ 0),\ (x_1,\ y_1)\ =\ (0,\ -1),\ (x_2,\ y_2)\ =\ (2,\ -1) $ . ### Sample Explanation 7 There may be duplicated points among $ (X_j,\ Y_j) $ .