题目描述

すぬけ君の工場では，次のような特徴を持つ ロボットアーム を導入することになりました：

• ロボットアームは，$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$ を到達させるためのモードの指定方法を求めてください．

输入格式

入力は以下の形式で標準入力から与えられる．

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

题目大意

给定 $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$

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$ が成り立つ．

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)$ の中に同じ点が含まれることもあります．