Problem:
 Score : 600 points    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 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       Partial Score  In the test cases worth 300 points, -10 \leq X_i \leq 10 and -10 \leq Y_i \leq 10 hold.         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 .        Sample Input 1 3
-1 0
0 3
2 -1      Sample Output 1 2
1 2
RL
UU
DR  In the given way to bring Joint m of the robot arm to each (X_j, Y_j) , the positions of the joints will be as follows:   To (X_1, Y_1) = (-1, 0) : First, the position of Joint 0 is (x_0, y_0) = (0, 0) . As the mode of Section 1 is R , the position of Joint 1 is (x_1, y_1) = (1, 0) . Then, as the mode of Section 2 is L , the position of Joint 2 is (x_2, y_2) = (-1, 0) .  To (X_2, Y_2) = (0, 3) : (x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3) .  To (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 Input 2 5
0 0
1 0
2 0
3 0
4 0      Sample Output 2 -1       Sample Input 3 2
1 1
1 1      Sample Output 3 2
1 1
RU
UR  There may be duplicated points among (X_j, Y_j) .       Sample Input 4 3
-7 -3
7 3
-3 -7      Sample Output 4 5
3 1 4 1 5
LRDUL
RDULR
DULRD

Solution (Python):
N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
Y=set()
B=[[1,1] for i in range(N)]
for i in range(N):
  for j in range(2):
    if X[i][j]<0:
      B[i][j]=0
      X[i][j]*=-1
for i in range(N):
  Y.add(sum(X[i])&1)
if len(Y)==2:
  print(-1)
  exit()
Y=Y.pop()
def f(x):
  r=[]
  y=x
  for i in range(20):
    r.append(y%3)
    y//=3
  return r

P=[[] for i in range(N)]
if Y:
  print(39)
  print(*[3**(i//2) for i in range(39)],sep=' ')
else:
  print(40)
  print(*[3**(i//2) for i in range(40)],sep=' ')
Z=[[f(X[i][0]),f(X[i][1])] for i in range(N)]
V=0
for i in range(N):
  V=[0]*2
  for j in range(20):
    for k in range(2):
      Z[i][k][j]+=V[k]
      V[k]=Z[i][k][j]//3
      Z[i][k][j]%=3
    if Z[i][0][j]==0:
      if Z[i][1][j]==0:
        P[i].append('R')
        P[i].append('L')
      elif Z[i][1][j]==1:
        P[i].append('U')
        P[i].append('U')
        V[1]+=1
      else:
        P[i].append('D')
        P[i].append('D')
    elif Z[i][0][j]==1:
      if Z[i][1][j]==0:
        P[i].append('R')
        P[i].append('R')
        V[0]+=1
      elif Z[i][1][j]==1:
        P[i].append('D')
        P[i].append('L')
      else:
        P[i].append('L')
        P[i].append('U')
        V[1]+=1
    else:
      if Z[i][1][j]==0:
        P[i].append('L')
        P[i].append('L')
      elif Z[i][1][j]==1:
        P[i].append('D')
        P[i].append('R')
        V[0]+=1
      else:
        P[i].append('R')
        P[i].append('U')
        V[1]+=1
        V[0]+=1
    if j==18 and Y:
      break
  if Y:
    if V[0]:
      P[i].append('L')
    else:
      P[i].append('D')
for i in range(N):
  for j in range(len(P[0])):
    if P[i][j]=='L':
      if B[i][0]:
        P[i][j]='R'
    elif P[i][j]=='R':
      if B[i][0]:
        P[i][j]='L'
    elif P[i][j]=='U':
      if B[i][1]:
        P[i][j]='D'
    else:
      if B[i][1]:
        P[i][j]='U'
  print(*P[i],sep='')

Solution (Python):



import numpy as np

def canbe_solved(positions):
    odd_evens = [np.dot(p,np.ones(2,int)) %2 for p in positions]
    if len(set(odd_evens)) == 1:
        return True
    else:
        return False

def solutions(p,vals):
    u = np.dot(p, np.array([1,1]))
    v = np.dot(p, np.array([1,-1]))
    for val in vals:
        if u >=0:
            if v >= 0:
                print('R',end="")
                u -= val
                v -= val
            else:
                print('U',end="")
                u -= val
                v += val
        else:
            if v >= 0:
                print('D',end="")
                u += val
                v -= val
            else:
                print('L',end="")
                u += val
                v += val
    print()
    
    
def main():
    
    n = int(input().rstrip())
    positions = [np.asarray(list(map(int,input().rstrip().split()))) for _ in range(n)]
    vals = [1<<i for i in range(30,-1,-1)]
    if np.dot(positions[0], np.ones(2,int)) % 2 == 0:
        vals.append(1)

    if canbe_solved(positions):
        print(len(vals))
        for i,p in enumerate(vals):
            print(p,end="")
            if i == len(vals)-1:
                print('')
            else:
                print(' ', end="")

        for p in positions:
            solutions(p,vals)
    else:
        print('-1')
        
main()

Solution (Python):
n = int(input())

chk = 0
pts = []
for i in range(n):
    x, y = map(int, input().split())
    if i == 0:
        chk = (x+y) % 2
    elif chk != (x+y) % 2:
        print(-1)
        exit()
    pts.append((x, y))

if chk:
    m = 35
    d = [2**i for i in range(35)]
else:
    m = 36
    d = [1] + [2**i for i in range(35)]

ans = []

for i in range(n):
    x, y = pts[i]
    pos = ['']*36
    u, v = x+y, x-y
    for j in range(35, -1, -1):
        if j == 35 and chk:
            continue
        if u >= 0 and v >= 0:
            u -= d[j]
            v -= d[j]
            pos[j] = 'R'
        elif u < 0 and v >= 0:
            u += d[j]
            v -= d[j]
            pos[j] = 'D'
        elif u <= 0 and v < 0:
            u += d[j]
            v += d[j]
            pos[j] = 'L'
        elif u > 0 and v < 0:
            u -= d[j]
            v += d[j]
            pos[j] = 'U'
    ans.append(''.join(pos))

print(m)
print(*d)

for x in ans:
    print(x)

Solution (Python):
n = int(input())

x = []
y = []

parity = -1
Have = True

for i in range(n):
    s = input().split(' ')
    x.append(int(s[0]))
    y.append(int(s[1]))

    p = (x[i] + y[i] + 10**10) % 2

    if (parity < 0):
        parity = p
    if (parity != p):
        Have = False

def Abs(v):
    if (v > 0): return  v
    else:       return -v

if (Have == False):
    print("-1")
else:
    arms = []

    for i in range(39):
        arms.append(2 ** (38 - i))

    if (parity == 0):
        arms.append(1)
        for i in range(n):
            x[i] -= 1

    print(len(arms))

    for v in arms:
        print(v,end = " ")

    print("")

    dx = [-1,0,1,0]
    dy = [0,-1,0,1]
    dir = ['L','D','R','U']

    for i in range(n):
        posX = 0
        posY = 0
        for j in range(39):
            for k in range(4):
                nxtX = posX + dx[k] * arms[j]
                nxtY = posY + dy[k] * arms[j]

                if (Abs(x[i] - nxtX) + Abs(y[i] - nxtY) < arms[j]):
                    print(dir[k],end = "")
                    posX = nxtX
                    posY = nxtY
                    break

        if (parity == 0):
            print("R")
        else:
            print("")

Solution (Python):
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]
if len(set([(x+y)%2 for x,y in xy]))>1:
  print(-1)
  exit()
m=0
d=[]
if sum(xy[0])%2==0:
  m+=1
  d.append(1)
for i in range(39):
  m+=1
  d.append(2**i)
print(m)
print(' '.join(list(map(str,d))))
for x,y in xy:
  ans=''
  for dd in d[::-1]:
    if y>=abs(x):
      ans='U'+ans
      y-=dd
    elif y>x and y<-x:
      ans='L'+ans
      x+=dd
    elif y<=-abs(x):
      ans='D'+ans
      y+=dd
    else:
      ans='R'+ans
      x-=dd
  print(ans)

Solution (Python):
n = int(input())
a = [tuple(map(int, input().split())) for _ in range(n)]

s = set(map(lambda x: sum(map(abs, x)) % 2, a))
if len(s) >= 2:
    print(-1)
    exit()

if next(iter(s)) == 0:
    m = 33
else:
    m = 32

d = [2 ** i for i in range(32)]
if m > len(d):
    d.append(1)

print(m)
print(*d)

def fetch(x, y, i=31):
    if i == 0:
        return {(1, 0): 'R', (-1, 0): 'L', (0, 1): 'U', (0, -1): 'D'}[(x, y)]
    if abs(x - d[i]) + abs(y) < d[i]:
        return fetch(x - d[i], y, i - 1) + 'R'
    if abs(x + d[i]) + abs(y) < d[i]:
        return fetch(x + d[i], y, i - 1) + 'L'
    if abs(y - d[i]) + abs(x) < d[i]:
        return fetch(x, y - d[i], i - 1) + 'U'
    if abs(y + d[i]) + abs(x) < d[i]:
        return fetch(x, y + d[i], i - 1) + 'D'

for x, y in a:
    if m == 33:
        print(fetch(x + 1, y) + 'L')
    else:
        print(fetch(x, y))

Solution (Python):
import sys
d = [1 << i for i in range(30, -1, -1)]
N = int(input())
points = [list(map(int, input().split())) for i in range(N)]
f = [0, 0]
for tmp in points:
    state = (abs(tmp[0]) + abs(tmp[1])) & 1
    f[state] = 1
if f[0] and f[1]:
    print(-1)
    sys.exit()

if f[0]:
    d.append(1)


def conAns(x, y):
    res = ''
    for i in d:
        if abs(x) > abs(y):
            if x > 0:
                x -= i
                res += 'R'
            else:
                x += i
                res += 'L'
        else:
            if y > 0:
                y -= i
                res += 'U'
            else:
                y += i
                res += 'D'
    return res


print(len(d))
print(d[0], end='')
for i in range(1, len(d)):
    print(' ' + str(d[i]), end='')
print("")
for tmp in points:
    x, y = tmp
    res = conAns(x, y)
    print(res)

Solution (Python):
import sys

N = int(input())

XY = []
for i in range(N):

    X,Y = map(int,input().split())
    XY.append([X,Y])

    if i > 0 and sum(XY[-2]) % 2 != (X+Y) % 2:
        print (-1)
        sys.exit()

d = [1]

while d[-1] <= 10 ** 9:
    d.append(d[-1] * 2)

d.reverse()
if sum(XY[0]) % 2 == 0:
    d.append(1)

print (len(d))
print (" ".join(map(str,d)))
for loop in range(N):

    ans = ""
    nx = 0
    ny = 0
    dx = XY[loop][0]
    dy = XY[loop][1]
    difx = 0
    dify = 0
    
    for i in range(len(d)):

        nmin = float("inf")
        pl = ""
        difx = 0
        dify = 0

        if abs(nx - d[i] - dx) + abs(ny - dy) < nmin:
            nmin = abs(nx - d[i] - dx) + abs(ny - dy)
            difx =  -1 * d[i]
            dify = 0
            pl = "L"

        if abs(nx + d[i] - dx) + abs(ny - dy) < nmin:
            nmin = abs(nx + d[i] - dx) + abs(ny - dy)
            difx = d[i]
            dify = 0
            pl = "R"

        if abs(nx - dx) + abs(ny - d[i] - dy) < nmin:
            nmin = abs(nx - dx) + abs(ny - d[i] - dy)
            difx = 0
            dify = -1 * d[i]
            pl = "D"

        if abs(nx - dx) + abs(ny + d[i] - dy) < nmin:
            nmin = abs(nx - dx) + abs(ny + d[i] - dy)
            difx = 0
            dify = d[i]
            pl = "U"

        ans += pl
        nx += difx
        ny += dify

    print (ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
xy = [[int(i) for i in readline().split()] for _ in range(n)]

p = sum(xy[0])%2
for x,y in xy:
    if p != (x+y)%2:
        print(-1)
        exit()

d = [2**i for i in range(38,-1,-1)]
if not p: d += [1]

print(len(d))
print(*d)

for x,y in xy:
    ans = []
    xx = yy = 0
    for di in d:
        dx = x-xx
        dy = y-yy
        if dy > dx:
            if dy > -dx:
                ans.append("U")
                yy += di
            else:
                ans.append("L")
                xx -= di
        else:
            if -dy > dx:
                ans.append("D")
                yy -= di
            else:
                ans.append("R")
                xx += di
    print("".join(ans))

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

def abc103():
    N = int(input())
    U, V = [None] * N, [None] * N
    OK = True
    for i in range(N):
        x, y = map(int, input().split())
        u, v = x+y, x-y
        U[i], V[i] = u, v
        if i != 0:
            if f ^ (u%2):
                OK = False
        f = u%2
    if OK == False:
        print(-1)
        exit()
    D = [2**i for i in range(30, -1, -1)] + [1]*(f^1)
    print(len(D))
    print(*D)
    for u, v in zip(U, V):
        ans = []
        pu, pv = 0, 0
        for d in D:
            if pu <= u and pv <= v:
                pu += d
                pv += d
                ans.append('R')
            elif pu <= u and pv >= v:
                pu += d
                pv -= d
                ans.append('U')
            elif pu >= u and pv >= v:
                pu -= d
                pv -= d
                ans.append('L')
            elif pu >= u and pv <= v:
                pu -= d
                pv += d
                ans.append('D')
        print(*ans, sep = '')

abc103()

Solution (Python):
import math

N = int(input())
points = [list(map(int, input().split())) for _ in range(N)]

possible = 1
for i in range(N):
  if i == 0:
    parity_0 = sum(points[i]) % 2
  else:
    if sum(points[i]) % 2 != parity_0:
      print(-1)
      possible = 0
      break

if possible:
  farthest = max([abs(point[0]) + abs(point[1]) for point in points])
  m = math.ceil(math.log2(farthest + 1))
  d_list = [2**(m-i-1) for i in range(m)]
  if parity_0 == 0:
    m = m + 1
    d_list.append(1)
  print(m)
  print(" ".join(map(str,d_list)))
  uv = [[point[0] + point[1], point[0] - point[1]] for point in points]
  for i in range(N):
    u = uv[i][0]
    v = uv[i][1]
    w = ""
    for d in d_list:
      if u > 0:
        if v > 0:
          w += "R"
          u -= d
          v -= d
        else:
          w += "U"
          u -= d
          v += d
      else:
        if v > 0:
          w += "D"
          u += d
          v -= d
        else:
          w += "L"
          u += d
          v += d
    print(w)

Solution (Python):
def solve():
    N = int(raw_input())
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[i], Y[i] = (int(_) for _ in raw_input().split())
    
    m = 31
    d = [0] * m
    tmp = 1
    for i in range(m - 1, -1, -1):
        d[i] = tmp
        tmp *= 2
    
    quo = (X[0] + Y[0]) % 2
    if quo == 0:
        d.append(1)
        m += 1
    modes = [''] * N
    for i in range(0, N):
        tmp_x = X[i]
        tmp_y = Y[i]
        if (tmp_x + tmp_y) % 2 != quo:
            print '-1'
            return 0
        for j in range(m):
            leng = d[j]
            if abs(tmp_x) > abs(tmp_y):
                if tmp_x > 0:
                    modes[i] += 'R'
                    tmp_x -= leng
                else:
                    modes[i] += 'L'
                    tmp_x += leng
            else:
                if tmp_y > 0:
                    modes[i] += 'U'
                    tmp_y -= leng
                else:
                    modes[i] += 'D'
                    tmp_y += leng

    print str(m)
    for i in range(m):
        print d[i],
    print
    for i in range(N):
        print modes[i]

if __name__ == '__main__':
    solve()

Solution (Python):
def solve():
    N = int(raw_input())
    X = [0] * N
    Y = [0] * N
    for i in range(N):
        X[i], Y[i] = (int(_) for _ in raw_input().split())
    
    m = 31
    d = [0] * m
    tmp = 1
    for i in range(m - 1, -1, -1):
        d[i] = tmp
        tmp *= 2
    
    quo = (X[0] + Y[0]) % 2
    if quo == 0:
        d.append(1)
        m += 1
    modes = [''] * N
    for i in range(0, N):
        tmp_x = X[i]
        tmp_y = Y[i]
        if (tmp_x + tmp_y) % 2 != quo:
            print '-1'
            return 0
        for j in range(m):
            leng = d[j]
            if abs(tmp_x - leng) + abs(tmp_y) <= leng:
                modes[i] += 'R'
                tmp_x -= leng
            elif abs(tmp_x + leng) + abs(tmp_y) <= leng:
                modes[i] += 'L'
                tmp_x += leng
            elif abs(tmp_x) + abs(tmp_y - leng) <= leng:
                modes[i] += 'U'
                tmp_y -= leng
            else:
                modes[i] += 'D'
                tmp_y += leng

    print str(m)
    for i in range(m):
        print d[i],
    print
    for i in range(N):
        print modes[i]

if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]

if len(set([(x+y)%2 for x, y in xy])) > 1:
    print(-1)
    exit()

m = 0
d = []
if sum(xy[0])%2 == 0:
    m += 1
    d.append(1)
for i in range(39):
    m +=1
    d.append(2**i)
print(m)
print(' '.join(list(map(str, d))))

for x, y in xy:
    ans = ''
    for dd in d[::-1]:
        if y >= abs(x): 
            ans = 'U' + ans
            y -= dd
        elif y > x and y < -x: 
            ans = 'L' + ans
            x += dd
        elif y <= -abs(x): 
            ans = 'D' + ans
            y += dd
        else: 
            ans = 'R' + ans
            x -= dd
    print(ans)

Solution (Python):
from sys import stdin, exit

def l2(num):
    return 0 if num == 1 else l2(num // 2) + 1

def go(x, y, lv):
    return (
            '' if x == y == 0
            else go(x, y - (1 << lv), lv - 1) + 'U' if abs(y) > abs(x) and y > 0
            else go(x, y + (1 << lv), lv - 1) + 'D' if abs(y) > abs(x) and y < 0
            else go(x + (1 << lv), y, lv - 1) + 'L' if abs(x) > abs(y) and x < 0
            else go(x - (1 << lv), y, lv - 1) + 'R'
    )

n = int(stdin.readline())
a = [list(map(int, stdin.readline().split())) for i in range(n)]

parity = (a[0][0] + a[0][1]) % 2
for (x, y) in a:
    if (x + y) % 2 != parity:
        print("-1")
        exit(0)

base_ans = ''
d = []
if parity == 0:
    base_ans = 'U'
    d.append(1)
    a = list(map(lambda u: (u[0], u[1] - 1), a))

mx = max(map(lambda u: abs(u[0]) + abs(u[1]), a))
max_lv = l2(mx)
d.extend(1 << i for i in range(max_lv + 1))

print(len(d))
print(' '.join(map(str, d)))
for (x, y) in a:
    print(base_ans + go(x, y, max_lv))

Solution (Python):
N=int(input())
i=0
placelist=[]
for _ in range(N):
  placelist.append([int(x) for x in input().split()])

mode=(placelist[0][0]+placelist[0][1])%2
for x in placelist:
  if mode!=(x[0]+x[1])%2:
    print(-1)
    exit()

mlist=[2**i for i in range(32,-1,-1)]


if mode:
  m=33
else:
  m=34
  mlist.append(1)


print (m)
print (' '.join(list(map(str,mlist))))

for x,y in placelist:
  xarm=0
  yarm=0
  route=''
  for arm in mlist:
    if (x-xarm)+(y-yarm)>0:
      if (x-xarm)-(y-yarm)>0:
        route+='R'
        xarm+=arm
      else:
        route+='U'
        yarm+=arm
    elif (x-xarm)-(y-yarm)>0:
      route+='D'
      yarm-=arm
    else:
      route+='L'
      xarm-=arm
  print(route)

Solution (Python):
import sys
N = int(input())
u = []
v = []
for k in range(N):
  x, y = map(int, input().split())
  u.append(x + y)
  v.append(x - y)

mod = u[0] % 2

for k in range(1, N):
  if (u[k] % 2) != mod:
    print(-1)
    sys.exit()

if mod == 1:
  print(31)
  print(*[2**r for r in reversed(range(31))])
  for k in range(N):
    U = (u[k] + 2**31 - 1) / 2
    V = (v[k] + 2**31 - 1) / 2
    for r in reversed(range(31)):
      if U // 2**r == 1:
        U -= 2**r
        if V // 2**r == 1:
          V -= 2**r
          print('R', end='')
        else:
          print('U', end='')
      else:
        if V // 2**r == 1:
          V -= 2**r
          print('D', end='')
        else:
          print('L', end='')
    print('')
else:
  print(32)
  print(*([2**r for r in reversed(range(31))]+[1]))
  for k in range(N):
    U = (u[k] + 2**31) / 2 - 1
    V = (v[k] + 2**31) / 2 - 1
    for r in reversed(range(31)):
      if U // 2**r == 1:
        U -= 2**r
        if V // 2**r == 1:
          V -= 2**r
          print('R', end='')
        else:
          print('U', end='')
      else:
        if V // 2**r == 1:
          V -= 2**r
          print('D', end='')
        else:
          print('L', end='')
    print('R')

Solution (Python):











import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve(N, XYs):

    
    mod2 = [(x + y) % 2 for x, y in XYs]
    if min(mod2) != max(mod2):
        print(-1)
        return

    
    
    arms = [2 ** x for x in range(31)]
    if mod2[0] == 0:
        arms = [1] + arms
    arms.reverse()

    print(len(arms))
    print(*arms)
    for x, y in XYs:
        
        u, v = x + y, x - y
        

        ans = ''
        for arm in arms:

            before_x = (u + v) // 2
            before_y = (u - v) // 2

            if u > 0:
                u -= arm
            else:
                u += arm
            if v > 0:
                v -= arm
            else:
                v += arm

            after_x = (u + v) // 2
            after_y = (u - v) // 2

            
            
            if before_x == after_x:
                if before_y < after_y:
                    ch = 'D'
                else:
                    ch = 'U'
            else:
                if before_x < after_x:
                    ch = 'L'
                else:
                    ch = 'R'
            ans += ch

        print(ans)

        
        assert u == 0 and v == 0
        pos_x = pos_y = 0
        for d, arm in zip(ans, arms):
            if d == 'U': pos_y += arm
            elif d == 'D': pos_y -= arm
            elif d == 'L': pos_x -= arm
            elif d == 'R': pos_x += arm
        assert x == pos_x
        assert y == pos_y


N = int(input())
XYs = []
for n in range(N):
    x, y = map(int, input().split())
    XYs.append((x, y))
solve(N, XYs)

Solution (Python):
import sys

n = int(input())
ds = [list(map(int, input().split())) for _ in range(n)]
mod = (ds[0][0] + ds[0][1]) % 2
for i in range(2, n):
	if (ds[i][0] + ds[i][1]) % 2 != mod:
		print(-1)
		sys.exit()

if mod == 1:
	m = 31
	arms = [1<<i for i in range(31, 0, -1)]
else:
	m = 32
	arms = [1<<i for i in range(31, 0, -1)] + [2]

print(m)
print(*[a//2 for a in arms])

for q in range(n):
	x, y = ds[q][0], ds[q][1]
	ans = ""
	u, v = x+y + (1<<31) - 1, x-y + (1<<31) - 1
	if mod == 0:
		u, v = u-1, v-1
	u_li = []
	v_li = []
	for i in range(31, 0, -1):
		if u >= (1<<i):
			u_li.append(1)
			u -= (1<<i)
		else:
			u_li.append(0)
		if v >= (1<<i):
			v_li.append(1)
			v -= (1<<i)
		else:
			v_li.append(0)

	for i in range(31):
		if u_li[i] and v_li[i]:
			ans += "R"
		elif u_li[i]:
			ans += "U"
		elif v_li[i]:
			ans += "D"
		else:
			ans += "L"

	if mod == 0:
		ans += "R"

	print(ans)

Solution (Python):

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

*S, = map(sum, P)
if any((S[0] - S[i]) % 2 for i in range(N)):
    print("-1")
    exit(0)

M = 31
A = 2**M-1
d = (S[0] & 1) ^ 1

U = []
if d:
    U.append(1)
    print(M+1)
else:
    print(M)
b = 1
for i in range(M):
    U.append(b)
    b <<= 1
print(*U)

C = "LDUR".__getitem__
for x, y in P:
    x -= d
    u = (x + y + A) >> 1
    v = (x - y + A) >> 1

    R = []
    if d:
        R.append("R")
    b = 1
    for k in range(M):
        R.append(C(2*(u & b > 0)+(v & b > 0)))
        b <<= 1
    print(*R, sep='')

Solution (Python):
import sys

LEN_D = 31
CONST = 2**LEN_D - 1

N = int(input())
XYs = [tuple(map(int, input().split())) for _ in range(N)]

parities = [(X+Y) % 2 for X, Y in XYs]
if len(set(parities)) != 1:
    print(-1)
    sys.exit()

if parities[0]:
    m = LEN_D
    ds = [2**i for i in range(LEN_D)]
else:
    m = LEN_D + 1
    ds = [1] + [2**i for i in range(LEN_D)]
print(m)
print(*ds)

for X, Y in XYs:
    ws = []
    if (X+Y) % 2 == 0:
        X -= 1
        ws.append('R')
    u = ((X+Y) + CONST) // 2
    v = ((X-Y) + CONST) // 2
    for i in range(LEN_D):
        ws.append('LDUR'[((u>>i) & 1) * 2 + ((v>>i) & 1)])
    print(''.join(ws))

Solution (Python):
N = int(input())
points = [tuple(int(x) for x in input().split()) for _ in range(N)]
if any(abs(x + y) % 2 != abs(sum(points[0])) % 2 for x, y in points):
    print(-1)
    quit()
even_flag = abs(sum(points[0])) % 2 == 0
points = [(x + y, x - y) for x, y in points]

M = 31 + even_flag
print(M)
print(*([1] if even_flag else []) + [1 << i for i in range(31)])
d_uv = {(0, 0): "L", (1, 1): "R", (1, 0): "U", (0, 1): "D"}
for u, v in points:
    ans = []
    if even_flag:
        ans.append("R")
        u, v = u - 1, v - 1
    sum_d_u = (u + (1 << 31) - 1) // 2
    sum_d_v = (v + (1 << 31) - 1) // 2
    for i in range(31):
        u_flag = sum_d_u >> i & 1
        v_flag = sum_d_v >> i & 1
        ans.append(d_uv[u_flag, v_flag])
    print(''.join(ans))

Solution (Python):
N = int(input())
X,Y = [0]*N,[0]*N
U,V = [0]*N,[0]*N
mod = [0] * N
for i in range(N):
    X[i],Y[i] = map(int,input().split(" "))
    mod[i] = (X[i] + Y[i]) % 2
    U[i],V[i] = (X[i]+Y[i]),(X[i]-Y[i])

l = len(list(filter(lambda x: x == 1,mod)))

if l != 0 and l != N:
    print(-1)
    exit(0)


if l == 0:
    d = [ 1 << i for i in range(38,-1,-1) ] + [1]

else:
    d = [ 1 << i for i in range(39,-1,-1) ]

ans = []
for i in range(N):
    move = []
    curU,curV = 0,0
    for step in d:
        if curU <= U[i] and curV <= V[i]:
            curU += step
            curV += step
            move.append('R')

        elif curU > U[i] and curV <= V[i]:
            curU -= step
            curV += step
            move.append('D')

        elif curU <= U[i] and curV > V[i]:
            curU += step
            curV -= step
            move.append('U')

        elif curU > U[i] and curV > V[i]:
            curU -= step
            curV -= step
            move.append('L')

    ans.append(move)

print(len(d))
print(*d)
for i in range(N):
    print("".join(ans[i]))

Solution (Python):
import sys


denum = 39

ds = [pow(2, i) for i in range(denum)]
max_ds = sum(ds)

N = input()
rr = []
for line in sys.stdin:
    x, y = line.strip().split(" ")
    rr.append((int(x) + int(y), int(x) - int(y)))

md = rr[0][0] % 2
if md == 0:
    ds = [1] + ds
Rresult = []
for u, v in rr:
    if u % 2 != md:
        result = "-1"
        break
    result = ""
    if md == 0:
        result = result + "R"
        u -= 1
        v -= 1
    u = (u + max_ds) // 2
    v = (v + max_ds) // 2
    binu = bin(u)[2:][::-1]
    binv = bin(v)[2:][::-1]
    for i in range(denum):
        ui = 0
        if i < len(binu):
            ui = int(binu[i])
        vi = 0
        if i < len(binv):
            vi = int(binv[i])
        
        if ui == 1 and vi == 1:
            result = result + "R"
        if ui == 0 and vi == 0:
            result = result + "L"
        if ui == 1 and vi == 0:
            result = result + "U"
        if ui == 0 and vi == 1:
            result = result + "D"
    Rresult.append(result)

ds = [str(x) for x in ds]
if result == "-1":
    print(result)
else:
    print(len(Rresult[0]))
    print(' '.join(ds))
    print("\n".join(Rresult))

Solution (Python):
n = int(input())
e = [[int(_) for _ in input().split()] for _ in range(n)]

def recursiveOdd(x, y, str):
    p = 31 - len(str)
    if x == 0 and y == 0:
        return str
    elif abs(x) > abs(y):
        if x > 0:
            return recursiveOdd(x - 2**p, y, str + 'R')
        else:
            return recursiveOdd(x + 2**p, y, str + 'L')
    else:
        if y > 0:
            return recursiveOdd(x, y - 2**p, str + 'U')
        else:
            return recursiveOdd(x, y + 2**p, str + 'D')

mod = (e[0][0] + e[0][1]) % 2
for i in e:
    if (i[0] + i[1]) % 2 != mod:
        print(-1)
        exit()

d = [2 ** (31 - _) for _ in range(0, 32)]
if mod == 0:
    d.append(1)
print(len(d))
print(' '.join([str(_) for _ in d]))

if mod == 1:
    for xy in e:
        print(recursiveOdd(xy[0], xy[1], ''))
else:
    for xy in e:
        print(recursiveOdd(xy[0] - 1, xy[1], '') + 'R')

Solution (Python):


import math

def query(p, q, ds):
    p_dirs = []
    q_dirs = []
    for d in ds:
        p_dir = 1 if p>0 else -1
        q_dir = 1 if q>0 else -1

        p_dirs.append(p_dir)
        q_dirs.append(q_dir)

        p -= p_dir * d
        q -= q_dir * d

    res = ''
    for pd, qd in zip(p_dirs, q_dirs):
        if pd > 0 and qd > 0:
            res += 'R'
        elif pd > 0 and qd < 0:
            res += 'U'
        elif pd < 0 and qd > 0:
            res += 'D'
        else:
            res += 'L'

    print(res)


def solve():
    n = int(input())
    queries = [tuple(map(int, input().split())) for _ in range(n)]
    m = max(map(lambda x: abs(x[0]) + abs(x[1]), queries))
    a = list(map(lambda x: (abs(x[0]) + abs(x[1])) % 2, queries))
    if len(set(a)) != 1:
        print(-1)
        return
    ps = [t[0]+t[1] for t in queries]
    qs = [t[0]-t[1] for t in queries]

    n_arms = int(math.ceil(math.log2(m)))
    if ps[0] % 2 == 0:
        ds = [2**i for i in reversed(range(n_arms))] + [1]
    else:
        ds = [2**i for i in reversed(range(n_arms))]
    print(len(ds))
    print(' '.join(map(str, ds)))
    for p, q in zip(ps, qs):
        query(p, q, ds)

if __name__ == '__main__':
    solve()

Solution (Python):
N=int(input())
X=[0 for i in range(N)]
Y=[0 for i in range(N)]
U=[0 for i in range(N)]
V=[0 for i in range(N)]
for i in range(N):
    X[i],Y[i]=map(int,input().split())
flag=(X[0]+Y[0])%2
for i in range(N):
    if flag!=(X[i]+Y[i])%2:
        print(-1)
        exit()
    U[i]=X[i]+Y[i]+1-flag
    V[i]=X[i]-Y[i]+1-flag
m=31
d=[2**i for i in range(m)]
S=["" for i in range(N)]
T=["" for i in range(N)]
W=["" for i in range(N)]
for i in range(N):
    k=(U[i]+(2**31-1))//2
    w="0"*(31-len(bin(k)[2:]))+bin(k)[2:]
    S[i]=w
    k=(V[i]+(2**31-1))//2
    w="0"*(31-len(bin(k)[2:]))+bin(k)[2:]
    T[i]=w
for i in range(N):
    if flag==0:
        W[i]="L"
    for j in range(m)[::-1]:
        if (S[i][j],T[i][j])==("0","0"):
            W[i]=W[i]+"L"
        elif (S[i][j],T[i][j])==("1","1"):
            W[i]=W[i]+"R"
        elif (S[i][j],T[i][j])==("0","1"):
            W[i]=W[i]+"D"
        else:
            W[i]=W[i]+"U"
arm=[]
if flag==0:
    arm.append(1)
for i in range(m):
    arm.append(d[i])
print(len(arm))
print(" ".join([str(i) for i in arm]))
for i in range(N):
    print(W[i])