#!/bin/python3 import sys def validMove(n, i, j): if i <0 or i >=n: return False if j <0 or j >=n: return False return True name = ['UL', 'UR', 'R','LR', 'LL', 'L'] moveY = [-1, 1, 2, 1, -1, -2] moveX = [-2, -2, 0, 2, 2, 0] def findNextLevel(inputArray, parent, level, cur_level, n, i_end, j_end): outputArray = [] found = False for k in range(len(inputArray)): for i in range(6): if validMove(n, inputArray[k][0]+moveX[i], inputArray[k][1]+ moveY[i]): if inputArray[k][0]+moveX[i] == i_end and inputArray[k][1]+ moveY[i] == j_end: parent[inputArray[k][0]+moveX[i]][inputArray[k][1]+ moveY[i]] = inputArray[k] found = True break elif level[inputArray[k][0]+moveX[i]][inputArray[k][1]+ moveY[i]] == -1: level[inputArray[k][0]+moveX[i]][inputArray[k][1]+ moveY[i]] = cur_level +1 parent[inputArray[k][0]+moveX[i]][inputArray[k][1]+ moveY[i]] = inputArray[k] outputArray.append([inputArray[k][0]+moveX[i],inputArray[k][1]+moveY[i]]) #print("at ", inputArray[k], "move to", inputArray[k][0]+moveX[i], inputArray[k][1]+ moveY[i]) if found: break if found: return True elif len(outputArray) >0: found = found or findNextLevel(outputArray, parent, level, cur_level+1, n, i_end, j_end) return found def printShortestPath(n, i_start, j_start, i_end, j_end): parent = [[[-1, -1] for i in range(n) ] for j in range(n)] level = [[-1 for i in range(n)] for j in range(n)] cur_level = 0 level[i_start][j_start] = 0 found = findNextLevel([[i_start, j_start]], parent, level, cur_level, n, i_end, j_end) if found: start = [i_end, j_end] result = [] while start != [-1, -1]: temp = parent[start[0]][start[1]] delX = -temp[0]+ start[0] delY = -temp[1]+start[1] #print(delX, delY) for i in range(6): if [delX, delY] == [moveX[i], moveY[i]]: result.append(name[i]) break start = temp print(len(result)) strToWrite = "" for i in range(len(result)): strToWrite += result[len(result)-1-i] + " " print(strToWrite[:-1]) else: print("Impossible") 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)