# [ARC103B] Robot Arms

## 题目描述

[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$ .

## 输入输出样例

### 输入样例 #1

3
-1 0
0 3
2 -1

### 输出样例 #1

2
1 2
RL
UU
DR

### 输入样例 #2

5
0 0
1 0
2 0
3 0
4 0

### 输出样例 #2

-1

### 输入样例 #3

2
1 1
1 1

### 输出样例 #3

2
1 1
RU
UR

### 输入样例 #4

3
-7 -3
7 3
-3 -7

### 输出样例 #4

5
3 1 4 1 5
LRDUL
RDULR
DULRD

### 输入样例 #5

3
-1 0
0 3
2 -1

### 输出样例 #5

2
1 2
RL
UU
DR

### 输入样例 #6

5
0 0
1 0
2 0
3 0
4 0

### 输出样例 #6

-1

### 输入样例 #7

2
1 1
1 1

### 输出样例 #7

2
1 1
RU
UR

### 输入样例 #8

3
-7 -3
7 3
-3 -7

### 输出样例 #8

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)$ .