#!/bin/python3 import sys from collections import namedtuple Position = namedtuple('Position', ('i', 'j')) def printShortestPath(n, i_start, j_start, i_end, j_end): if i_start % 2 != i_end % 2: print('Impossible') return Move = namedtuple('Move', ('name', 'delta_i', 'delta_j')) s = Position(i_start, j_start) t = Position(i_end, j_end) moves = [Move('UL', -2, -1), Move('UR', -2, 1), Move('R', 0, 2), Move('LR', 2, 1), Move('LL', 2, -1), Move('L', 0, -2)] final_moves = BFS(n, moves, s, t) if final_moves is False: print('Impossible') else: print(len(final_moves)) print(*final_moves) def BFS(n, moves, s, t): if s == t: return [] parent = {s : None} move_dict = {} end = False # BFS frontier = [s] while frontier and not end: next_frontier = [] for pos in frontier: for m in moves: new_pos = Position(pos.i + m.delta_i, pos.j + m.delta_j) # Check if new_pos is in the grid if new_pos.i < 0 or new_pos.i >= n or new_pos.j < 0 or new_pos.j >= n: continue # Optimisation : Check if the new_pos is directly next to t in the row dimension if new_pos.i + 1 == t.i or new_pos.i - 1 == t.i: # Early termination we know the destination is unreachable with the moveset return False if new_pos not in parent: parent[new_pos] = pos move_dict[new_pos] = m.name next_frontier.append(new_pos) if new_pos == t: # Early termination if we are at the end destination end = True break if end: break frontier = next_frontier if t not in parent: return False final_moves = [] current = t while current in move_dict: final_moves.append(move_dict[current]) current = parent[current] final_moves.reverse() return final_moves 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)