[ABC111D] Robot Arms

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

[problemUrl]: https://atcoder.jp/contests/abc111/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 $ を到達させるためのモードの指定方法を求めてください．

入力は以下の形式で標準入力から与えられる． > $ 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

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