import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static class Coordinate { public int r; public int c; public Coordinate(int r, int c) { this.r = r; this.c = c; } } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { if (i_start == i_end && j_start == j_end) return; // Print the distance along with the sequence of moves. /* Do a BFS from (i_start, j_start). The order is UL, UR, R, LR, LL, L. Have a Helper Class called Step Step[][] parents = new Step[n][n] boolean[][] marked = new boolean[n][n] UL: r-2, c-1 UR: r-2, c+1 R: r, c+2 LR: r+2, c+1 LL: r+2, c-1 L: r, c-2 */ Queue q = new LinkedList<>(); Coordinate[][] parents = new Coordinate[n][n]; boolean[][] marked = new boolean[n][n]; Coordinate first = new Coordinate(i_start, j_start); q.offer(first); marked[i_start][j_start] = true; while (!q.isEmpty()) { Coordinate current = q.poll(); if (current.r == i_end && current.c == j_end) break; //UL Coordinate UL = new Coordinate(current.r-2, current.c-1); if (isValid(UL.r, UL.c, n) && !marked[UL.r][UL.c]) { marked[UL.r][UL.c] = true; parents[UL.r][UL.c] = current; q.offer(UL); } //UR Coordinate UR = new Coordinate(current.r-2, current.c+1); if (isValid(UR.r, UR.c, n) && !marked[UR.r][UR.c]) { marked[UR.r][UR.c] = true; parents[UR.r][UR.c] = current; q.offer(UR); } //R Coordinate R = new Coordinate(current.r, current.c+2); if (isValid(R.r, R.c, n) && !marked[R.r][R.c]) { marked[R.r][R.c] = true; parents[R.r][R.c] = current; q.offer(R); } //LR Coordinate LR = new Coordinate(current.r+2, current.c+1); if (isValid(LR.r, LR.c, n) && !marked[LR.r][LR.c]) { marked[LR.r][LR.c] = true; parents[LR.r][LR.c] = current; q.offer(LR); } //LL Coordinate LL = new Coordinate(current.r+2, current.c-1); if (isValid(LL.r, LL.c, n) && !marked[LL.r][LL.c]) { marked[LL.r][LL.c] = true; parents[LL.r][LL.c] = current; q.offer(LL); } //L Coordinate L = new Coordinate(current.r, current.c-2); if (isValid(L.r, L.c, n) && !marked[L.r][L.c]) { marked[L.r][L.c] = true; parents[L.r][L.c] = current; q.offer(L); } } if (!marked[i_end][j_end]) { System.out.println("Impossible"); return; } Stack reversePath = new Stack<>(); for (Coordinate p = new Coordinate(i_end, j_end); !(p.r == i_start && p.c == j_start); p = parents[p.r][p.c]) { reversePath.push(p); } reversePath.push(new Coordinate(i_start, j_start)); List path = new ArrayList<>(); //prints the length of the path System.out.println(reversePath.size()-1); while (!reversePath.isEmpty()) { path.add(reversePath.pop()); } for (int i = 1; i < path.size(); i++) { int r_diff = path.get(i).r - path.get(i-1).r; int c_diff = path.get(i).c - path.get(i-1).c; if (r_diff == -2 && c_diff == -1) { System.out.print("UL "); } if (r_diff == -2 && c_diff == 1) { System.out.print("UR "); } if (r_diff == 0 && c_diff == 2) { System.out.print("R "); } if (r_diff == 2 && c_diff == 1) { System.out.print("LR "); } if (r_diff == 2 && c_diff == -1) { System.out.print("LL "); } if (r_diff == 0 && c_diff == -2) { System.out.print("L "); } } } public static boolean isValid(int r, int c, int n) { return r >= 0 && r < n && c >= 0 && c < 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(); } }