1 atcoder#ARC103B. [ABC111D] Robot Arms

[ABC111D] Robot Arms

Score : 600600 points

Problem Statement

Snuke is introducing a robot arm with the following properties to his factory:

  • The robot arm consists of mm sections and m+1m+1 joints. The sections are numbered 11, 22, ..., mm, and the joints are numbered 00, 11, ..., mm. Section ii connects Joint i1i-1 and Joint ii. The length of Section ii is did_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 ii will be determined as follows (we denote its coordinates as (xi,yi)(x_i, y_i)):- (x0,y0)=(0,0)(x_0, y_0) = (0, 0).
    • If the mode of Section ii is L, (xi,yi)=(xi1di,yi1)(x_{i}, y_{i}) = (x_{i-1} - d_{i}, y_{i-1}).
    • If the mode of Section ii is R, (xi,yi)=(xi1+di,yi1)(x_{i}, y_{i}) = (x_{i-1} + d_{i}, y_{i-1}).
    • If the mode of Section ii is D, (xi,yi)=(xi1,yi1di)(x_{i}, y_{i}) = (x_{i-1}, y_{i-1} - d_{i}).
    • If the mode of Section ii is U, (xi,yi)=(xi1,yi1+di)(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 mm can be matched with all of the NN points (X1,Y1),(X2,Y2),...,(XN,YN)(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 mm to each point (Xj,Yj)(X_j, Y_j).

Constraints

  • All values in input are integers.
  • 1N10001 \leq N \leq 1000
  • 109Xi109-10^9 \leq X_i \leq 10^9
  • 109Yi109-10^9 \leq Y_i \leq 10^9

Partial Score

  • In the test cases worth 300300 points, 10Xi10-10 \leq X_i \leq 10 and 10Yi10-10 \leq Y_i \leq 10 hold.

Input

Input is given from Standard Input in the following format:

NN

X1X_1 Y1Y_1

X2X_2 Y2Y_2

::

XNX_N YNY_N

Output

If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print -1.

mm

d1d_1 d2d_2 ...... dmd_m

w1w_1

w2w_2

::

wNw_N

mm and did_i are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, 1m401 \leq m \leq 40 and 1di10121 \leq d_i \leq 10^{12} must hold. Also, mm and did_i must all be integers.

wjw_j is a string of length mm that represents the way to bring Joint mm of the robot arm to point (Xj,Yj)(X_j, Y_j). The ii-th character of wjw_j should be one of the letters L, R, D and U, representing the mode of Section ii.

3
-1 0
0 3
2 -1
2
1 2
RL
UU
DR

In the given way to bring Joint mm of the robot arm to each (Xj,Yj)(X_j, Y_j), the positions of the joints will be as follows:

  • To (X1,Y1)=(1,0)(X_1, Y_1) = (-1, 0): First, the position of Joint 00 is (x0,y0)=(0,0)(x_0, y_0) = (0, 0). As the mode of Section 11 is R, the position of Joint 11 is (x1,y1)=(1,0)(x_1, y_1) = (1, 0). Then, as the mode of Section 22 is L, the position of Joint 22 is (x2,y2)=(1,0)(x_2, y_2) = (-1, 0).
  • To (X2,Y2)=(0,3)(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 (X3,Y3)=(2,1)(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

There may be duplicated points among (Xj,Yj)(X_j, Y_j).

3
-7 -3
7 3
-3 -7
5
3 1 4 1 5
LRDUL
RDULR
DULRD