# AtCoder ARC 103 D - Robot Arms

## Problem Statement

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

The robot arm consists of m sections and m+1 joints. The sections are numbered 1, 2, …, m, and the joints are numbered 0, 1, …, m. Section i connects Joint i−1 and Joint i. The length of Section i is di.
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 i will be determined as follows (we denote its coordinates as $$(x_i,y_i)$$):
$$(x_0,y_0)=(0,0)$$.

• If the mode of Section i is L, $$(x_i,y_i)=(x_i−1−d_i,y_i−1)$$.
• If the mode of Section i is R, $$(x_i,y_i)=(x_i−1+d_i,y_i−1)$$.
• If the mode of Section i is D, $$(x_i,y_i)=(x_i−1,y_i−1−d_i)$$.
• If the mode of Section i is U, $$(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 m can be matched with all of the N points $$(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 m to each point $$(X_j,Y_j)$$.

## Constraints

All values in input are integers.
$$1≤N \le 1000$$
$$−10^9 \le X_i \le 10^9$$
$$−10^9 \le Y_i \le 10^9$$
Partial Score
In the test cases worth 300 points, $$−10 \le Xi \le 10$$ and $$−10 \le Y_i \le 10$$ hold.

## Sample Input

3
-1 0
0 3
2 -1


## Sample Output

2
1 2
RL
UU
DR


## Solution

） → {1,2,4,…,2^{k-1}}，2^k。

## Code

#include <cstdio>
#include <algorithm>
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 100005;
const int P = 1000000007;
const double eps = 1e-6;
using namespace std;
inline int getint() {
int r = 0; bool b = true; char c = getchar();
while (c < '0' || c > '9') { if (c == '-') b = false; c = getchar(); }
while (c >= '0' &amp;&amp; c <= '9') { r = (r<<1)+(r<<3) + c - '0'; c = getchar(); }
return b ? r : -r;
}
int n;
int x[MAXN], y[MAXN];
int cnt, mx[MAXN];
char dst[MAXN];
int main() {
n = getint();
for (int i = 0; i < n; ++i) {
x[i] = getint();
y[i] = getint();
}
int b = (abs(x[0] + y[0]) &amp; 1);
for (int i = 1; i < n; ++i)
if ((abs(x[i] + y[i]) &amp; 1) != b) {
puts("-1");
return 0;
}
printf("%d\n", 32 - b);
dst[0] = 1;
if (b == 0) printf("1 ");
mx[0] = 0;
for (int i = 1; i < 31; ++i)
mx[i] = mx[i-1] * 2 + 1;
for (int i = 0; i < 31; ++i)
printf("%d ", (1<<i));
putchar('\n');
for (int i = 0; i < n; ++i) {
int X = x[i], Y = y[i];
if (b == 0) {
putchar('R');
--X;
}
cnt = 0;
for (int j = 30; j >= 0; --j) {
if ((LL) abs(X + (1<<j)) + abs(Y) <= (LL) mx[j]) {
dst[++cnt] = 'L';
X += (1<<j);
continue;
}
if ((LL) abs(X - (1<<j)) + abs(Y) <= (LL) mx[j]) {
dst[++cnt] = 'R';
X -= (1<<j);
continue;
}
if ((LL) abs(X) + abs(Y + (1<<j)) <= (LL) mx[j]) {
dst[++cnt] = 'D';
Y += (1<<j);
continue;
}
if ((LL) abs(X) + abs(Y - (1<<j)) <= (LL) mx[j]) {
dst[++cnt] = 'U';
Y -= (1<<j);
continue;
}
}
for (int j = cnt; j >= 1; --j) putchar(dst[j]);
putchar('\n');
}
}