Problem: 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 d_i.
* 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 \leq N \leq 1000
* -10^9 \leq X_i \leq 10^9
* -10^9 \leq Y_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
X_1 Y_1
X_2 Y_2
:
X_N Y_N


Output

If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print `-1`.


m
d_1 d_2 ... d_m
w_1
w_2
:
w_N


m and d_i are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, 1 \leq m \leq 40 and 1 \leq d_i \leq 10^{12} must hold. Also, m and d_i must all be integers.

w_j is a string of length m that represents the way to bring Joint m of the robot arm to point (X_j, Y_j). The i-th character of w_j should be one of the letters `L`, `R`, `D` and `U`, representing the mode of Section i.

Examples

Input

3
-1 0
0 3
2 -1


Output

2
1 2
RL
UU
DR


Input

5
0 0
1 0
2 0
3 0
4 0


Output

-1


Input

2
1 1
1 1


Output

2
1 1
RU
UR


Input

3
-7 -3
7 3
-3 -7


Output

5
3 1 4 1 5
LRDUL
RDULR
DULRD

Solution (in PYTHON3):

Solution:
import sys
def input(): return sys.stdin.readline().strip()

def direction_odd(x, y, m):
    """
    m本の腕で(0, 0)から(x, y)に移動する手順を出力する（x + yは奇数を想定）
    """
    ans = ""
    for i in range(m - 1, -1, -1):
        if y < x and y > -x:
            ans += "R"
            x -= 2 ** i
        elif y > x and y > -x:
            ans += "U"
            y -= 2 ** i
        elif y > x and y < -x:
            ans += "L"
            x += 2 ** i
        elif y < x and y < -x:
            ans += "D"
            y += 2 ** i
    return ans

def direction_even(x, y, m):
    if y <= x and y >= -x:
        last = "R"
        x -= 1
    elif y >= x and y >= -x:
        last = "U"
        y -= 1
    elif y >= x and y <= -x:
        last = "L"
        x += 1
    elif y <= x and y <= -x:
        last = "D"
        y += 1
    ans = direction_odd(x, y, m)
    return ans + last


def main():
    N = int(input())
    joint = []
    for _ in range(N):
        x, y = map(int, input().split())
        joint.append((x, y))
    
    """
    まず移動可能な頂点の１つを(x, y)として、(x, y)は\pm (dx, dy)の総和として求まるので
    mod 2でx+yは到着可能な位置に依らず不変量になる。
    なので到着したい位置N子に対してx+yの偶奇がすべて一致するかをまずチェックすれば、それで
    答えが-1になるケースは正答できる。

    問題はこの偶奇がすべて一致している場合だが、実はその場合は必ず題を満たすロボットアームが作れる。
    まず直感として最初に長い腕で移動してからだんだん長さの短い腕で微調整すればよさそうである。
    これを２べきにそろえると、なんと到着可能点がぴったり市松模様になる！！！
    """

    even_odd = {0: 0, 1: 0}
    sum_max = 0
    for x, y in joint:
        even_odd[(x + y) % 2] += 1
        sum_max = max(sum_max, abs(x) + abs(y))
    if even_odd[0] > 0 and even_odd[1] > 0:
        print(-1)
        return

    m = 0
    while (2 ** m - 1 < sum_max): m += 1
    arms = [2 ** i for i in range(m - 1, -1, -1)]
    if even_odd[0] == 0:
        print(m)
        print(" ".join(map(str, arms)))
        for x, y in joint: print(direction_odd(x, y, m))
    if even_odd[0] != 0:
        print(m + 1)
        print(" ".join(map(str, arms)) + " 1")
        for x, y in joint: print(direction_even(x, y, m))
    

if __name__ == "__main__":
    main()