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

输入输出样例

输入样例 #1

3
-1 0
0 3
2 -1

输出样例 #1

2
1 2
RL
UU
DR

输入样例 #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

输入样例 #4

3
-7 -3
7 3
-3 -7

输出样例 #4

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