import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; import java.util.Scanner; import java.util.stream.Collectors; public class Solution { private static String[] direction = {"UL", "UR", "R", "LR", "LL", "L"}; private static int[] neiRow = {-2, -2, 0, 2, 2, 0}; private static int[] neiCol = {-1, 1, 2, 1, -1, -2}; private 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. int[][] pathLength = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { pathLength[i][j] = -1; } } pathLength[i_start][j_start] = 0; String[][] pathDirection = new String[n][n]; pathDirection[i_start][j_start] = ""; fillPaths(pathLength, pathDirection, i_start, j_start, n); String finalDir = pathDirection[i_end][j_end]; if (finalDir != null) { System.out.println(pathLength[i_end][j_end]); System.out.println(Arrays.stream(finalDir.split("")) .mapToInt(Integer::valueOf) .mapToObj(d -> direction[d]) .collect(Collectors.joining(" "))); } else { System.out.println("Impossible"); } } private static void fillPaths(int[][] pathLength, String[][] pathDirection, int i, int j, int n) { Queue rowIndex = new ArrayDeque<>(); Queue colIndex = new ArrayDeque<>(); for (int k = 0; k < direction.length; k++) { int neibour_i = i + neiRow[k]; int neibour_j = j + neiCol[k]; if (isValid(neibour_i, neibour_j, n) && pathLength[neibour_i][neibour_j] == -1) { rowIndex.add(neibour_i); colIndex.add(neibour_j); pathLength[neibour_i][neibour_j] = pathLength[i][j] + 1; pathDirection[neibour_i][neibour_j] = pathDirection[i][j] + Integer.toString(k); } } while (!rowIndex.isEmpty()) { int curRow = rowIndex.poll(); int curCol = colIndex.poll(); for (int k = 0; k < direction.length; k++) { int neibour_i = curRow + neiRow[k]; int neibour_j = curCol + neiCol[k]; if (isValid(neibour_i, neibour_j, n) && pathLength[neibour_i][neibour_j] == -1) { rowIndex.add(neibour_i); colIndex.add(neibour_j); pathLength[neibour_i][neibour_j] = pathLength[curRow][curCol] + 1; pathDirection[neibour_i][neibour_j] = pathDirection[curRow][curCol] + Integer.toString(k); } } } } private static boolean isValid(int i, int j, int n) { return i >= 0 && i < n && j >= 0 && j < 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(); } }