#!/bin/python3 import sys # UL, UR, R, LR, LL, L # i - row, j - column def printShortestPath(n, i_start, j_start, i_end, j_end): path = find_path(i_start, j_start, curr_min) if path is None: print('Impossible') else: print(path[0]) for move in path[1]: if move == 'UL': print(move,end=' ') path[1].remove(move) for move in path[1]: if move == 'UR': print(move,end=' ') path[1].remove(move) for move in path[1]: if move == 'R': print(move,end=' ') path[1].remove(move) for move in path[1]: if move == 'LR': print(move,end=' ') path[1].remove(move) for move in path[1]: if move == 'LL': print(move,end=' ') path[1].remove(move) for move in path[1]: print(move,end=' ') def find_path(curr_i, curr_j, curr_min: list, curr_moves=0): if curr_moves >= curr_min[0]: return None elif n < curr_i or curr_i < 0 or n < curr_j or curr_j < 0: return None elif curr_i == i_e and curr_j == j_e: curr_min[0] = curr_moves return (0, []) else: list_moves = [] if curr_i > i_e: if curr_j >= j_e: m = get_move('UL', curr_i, curr_j) UL_move = find_path(m[0], m[1], curr_min, curr_moves + 1) UR_move = None else: UL_move = None m = get_move('UR', curr_i, curr_j) UR_move = find_path(m[0], m[1], curr_min, curr_moves + 1) else: UR_move = None UL_move = None if curr_j < j_e and j_e - curr_j > 1 and curr_i == i_e: m = get_move('R', curr_i, curr_j) R_move = find_path(m[0], m[1], curr_min, curr_moves + 1) else: R_move = None if curr_i < i_e: if curr_j <= j_e: m = get_move('LR', curr_i, curr_j) LR_move = find_path(m[0], m[1], curr_min, curr_moves + 1) LL_move = None else: m = get_move('LL', curr_i, curr_j) LL_move = find_path(m[0], m[1], curr_min, curr_moves + 1) LR_move = None else: LR_move = None LL_move = None if curr_j > j_e and curr_j - j_e > 1 and curr_i == i_e: m = get_move('L', curr_i, curr_j) L_move = find_path(m[0], m[1], curr_min, curr_moves + 1) else: L_move = None lst_possible = [UL_move, UR_move, R_move, LR_move, LL_move, L_move] final_move = None for move in lst_possible: if move is not None and (final_move is None or final_move[0] > move[0]): final_move = move if final_move is not None: if final_move is UL_move: list_moves.append('UL') elif final_move is UR_move: list_moves.append('UR') elif final_move is R_move: list_moves.append('R') elif final_move is LR_move: list_moves.append('LR') elif final_move is LL_move: list_moves.append('LL') elif final_move is L_move: list_moves.append('L') list_moves.extend(final_move[1]) return (1 + final_move[0], list_moves) else: return None def get_move(move, curr_i, curr_j): if move == 'UL': return curr_i - 2, curr_j - 1 elif move == 'UR': return curr_i - 2, curr_j + 1 elif move == 'R': return curr_i, curr_j + 2 elif move == 'LR': return curr_i + 2, curr_j + 1 elif move == 'LL': return curr_i + 2, curr_j - 1 elif move == 'L': return curr_i, curr_j - 2 if __name__ == "__main__": n = int(input().strip()) curr_min = [n + 2] 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)] i_e = i_end j_e = j_end printShortestPath(n, i_start, j_start, i_end, j_end)