配点 : $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$ のモードを表す．

3
-1 0
0 3
2 -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)$ です．

5
0 0
1 0
2 0
3 0
4 0

-1

2
1 1
1 1

2
1 1
RU
UR

$(X_j, Y_j)$ の中に同じ点が含まれることもあります．

3
-7 -3
7 3
-3 -7

5
3 1 4 1 5
LRDUL
RDULR
DULRD