/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
すぬけ君の工場では，次のような特徴を持つ ロボットアーム を導入することになりました：
- ロボットアームは，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 を到達させるためのモードの指定方法を求めてください．
制約
- 入力はすべて整数である
- 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 が成り立つ．
入力
入力は以下の形式で標準入力から与えられる．
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 文字からなる文字列であり，点 (X_j, Y_j) にロボットアームの関節 m を到達させる方法を表す．
w_j の i 文字目は L, R, D, U のいずれかの文字であり，腕 i のモードを表す．
入力例 1
3 -1 0 0 3 2 -1
出力例 1
2 1 2 RL UU DR
それぞれの (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) です．
入力例 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
(X_j, Y_j) の中に同じ点が含まれることもあります．
入力例 4
3 -7 -3 7 3 -3 -7
出力例 4
5 3 1 4 1 5 LRDUL RDULR DULRD
Score : 600 points
Problem Statement
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,DandU. 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).
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.
Input
Input is given from Standard Input in the following format:
N X_1 Y_1 X_2 Y_2 : X_N Y_N
Output
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.
Sample Input 1
3 -1 0 0 3 2 -1
Sample Output 1
2 1 2 RL UU DR
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 isL, 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 Input 2
5 0 0 1 0 2 0 3 0 4 0
Sample Output 2
-1
Sample Input 3
2 1 1 1 1
Sample Output 3
2 1 1 RU UR
There may be duplicated points among (X_j, Y_j).
Sample Input 4
3 -7 -3 7 3 -3 -7
Sample Output 4
5 3 1 4 1 5 LRDUL RDULR DULRD