#!/bin/python3 import sys from collections import deque def reachable(i_start, j_start, i_end, j_end): # By taking the difference we put the start at the origin, # yielding this reachability pattern: # # _0_1_0_1_0_1 (col mod 2) # 0|- 0 - 0 - 0 # 1|0 0 0 0 0 0 # 2|0 - 0 - 0 - # 3|0 0 0 0 0 0 # 0|- 0 - 0 - 0 # (row mod 4) i_mod = abs(i_end - i_start) % 4 j_mod = abs(j_end - j_start) % 2 return (i_mod == j_mod == 0) or (i_mod == 2 and j_mod == 1) def printShortestPath(n, i_start, j_start, i_end, j_end): if not reachable(i_start, j_start, i_end, j_end): print("Impossible") else: move_names = {(-2, -1): "UL", (-2, 1): "UR", (0, 2): "R", (2, 1): "LR", (2, -1): "LL", (0, -2): "L"} path = shortestPath(n, i_start, j_start, i_end, j_end) print(len(path)) print(" ".join(move_names[p] for p in path)) def between(n, x, y): # Inclusive between return (y >= x and x <= n <= y) or (y < x and y <= n <= x) def shortestPath(n, i_start, j_start, i_end, j_end): end = (i_end, j_end) def good_moves(loc): # (delta_row, delta_col) for i, j in [(-2, -1), (-2, 1), (0, 2), (2, 1), (2, -1), (0, -2)]: ni = loc[0] + i nj = loc[1] + j if 0 <= ni < n and 0 <= nj < n and (between(ni, end[0], loc[0]) or between(nj, end[1], loc[1])): yield (ni, nj) def history(shortest_paths, loc): new_loc = shortest_paths[loc] path = [] while new_loc is not None: path.append((loc[0]-new_loc[0], loc[1]-new_loc[1])) loc = new_loc new_loc = shortest_paths[loc] return list(reversed(path)) shortest_paths = {(i_start, j_start): None} q = deque([(i_start, j_start)]) while True: loc = q.popleft() for nloc in good_moves(loc): if nloc not in shortest_paths: shortest_paths[nloc] = loc q.append(nloc) if nloc == end: return history(shortest_paths, end) if __name__ == "__main__": n = int(input().strip()) i_start, j_start, i_end, j_end = input().strip().split(' ') i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)] printShortestPath(n, i_start, j_start, i_end, j_end)