import java.util.Arrays; import java.util.HashMap; import java.util.Scanner; import java.util.Stack; public class Solution { private static String movement[] = new String[] { "UL", "UR", "R", "LR", "LL", "L" }; private static int movementX[] = new int[] { -2, -2, 0, 2, 2, 0 }; private static int movementY[] = new int[] { -1, 1, 2, 1, -1, -2 }; private static int matrix[][]; private static int N; private static HashMap state = new HashMap<>(); static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. N = n; matrix = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = -1; } } matrix[i_start][j_start] = 0; dfs(i_start, j_start, ""); if (matrix[i_end][j_end] == -1) { System.out.println("Impossible"); return; } System.out.println(matrix[i_end][j_end]); String path = state.get(i_end + "," + j_end); String[] moves = path.split("-"); StringBuilder builder = new StringBuilder(); for (int i = 0; i < moves.length; i++) { builder.append(movement[Integer.valueOf(moves[i])]); if (i < moves.length - 1) { builder.append(" "); } } System.out.print(builder.toString()); // for (int i = 0; i < n; i++) { // System.out.println(Arrays.toString(matrix[i])); // } } private static void dfs(int x, int y, String path) { // System.out.println(path); for (int i = 0; i < 6; i++) { int nextX = x + movementX[i]; int nextY = y + movementY[i]; if (isValid(nextX, nextY, N)) { String newPath; if (path.equals("")) { newPath = path + i; } else { newPath = path + "-" + i; } if (matrix[nextX][nextY] == -1) { matrix[nextX][nextY] = matrix[x][y] + 1; state.put(nextX + "," + nextY, newPath); dfs(nextX, nextY, newPath); } else if (matrix[x][y] + 1 < matrix[nextX][nextY]) { matrix[nextX][nextY] = matrix[x][y] + 1; state.put(nextX + "," + nextY, newPath); dfs(nextX, nextY, newPath); } else if (matrix[x][y] + 1 == matrix[nextX][nextY]) { String oldState = state.get(nextX + "," + nextY); String[] splitOldState = oldState.split("-"); String[] splitNewState = newPath.split("-"); boolean betterWay = false; for (int k = 0; k < splitNewState.length; k ++) { int oldMove = Integer.valueOf(splitOldState[0]); int newMove = Integer.valueOf(splitNewState[0]); if (newMove < oldMove) { betterWay = true; break; } } if (betterWay) { dfs(nextX, nextY, newPath); } // System.out.println(Arrays.toString(splitOldState)); // System.out.println(Arrays.toString(splitNewState)); } } } } private static boolean isValid(int x, int y, int n) { return x >= 0 && y >= 0 && x < n && y < n; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int i_start = in.nextInt(); int j_start = in.nextInt(); int i_end = in.nextInt(); int j_end = in.nextInt(); printShortestPath(n, i_start, j_start, i_end, j_end); in.close(); } }