import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static boolean printShortestPath(int n, int i_start, int j_start, int i_end, int j_end, Stack res){ boolean c = false; // if exactly on left or right if(i_start == i_end){ //System.out.println("0"); //System.out.println(i_start + " "+ j_start + " "+ i_end + " "+ j_end); if(Math.abs(j_start-j_end) %2 == 1){ return false; } else if(j_end == j_start){ //System.out.println("after 0"); return true; } else if(j_end < j_start){ res.push("L"); c = printShortestPath(n, i_start, j_start-2, i_end, j_end, res); } else{ res.push("R"); c = printShortestPath(n, i_start, j_start+2, i_end, j_end, res); } } // if end is on top left, UL // or // if end is on top exactly, UL else if(i_end < i_start && j_end <= j_start ) { //System.out.println("1"); if(j_end == j_start && (i_start-2 >=0 && j_start-1>=0)){ res.push("UL"); c = printShortestPath(n, i_start-2, j_start-1, i_end, j_end, res); } else if(i_start-2 >= 0 && j_start-1>=0 ){ res.push("UL"); c = printShortestPath(n, i_start-2, j_start-1, i_end, j_end, res); }else{ return false; } } // if end is on top right, UR else if(i_end < i_start && j_end > j_start ) { //System.out.println("2"); if(i_start-2 >= 0 && j_start+1 <= j_end ){ res.push("UR"); c = printShortestPath(n, i_start-2, j_start+1, i_end, j_end, res); }else{ return false; } } // if end is on bottom right, LR // or // if end is on bottom exactly,LR else if( i_end > i_start && j_end >= j_start ) { //System.out.println("3"); // if it's right at the bottom if(j_end == j_start && (i_start+2 < n && j_start+1 < n) ){ res.push("LR"); c = printShortestPath(n, i_start+2, j_start+1, i_end, j_end, res); } else if(i_start+2 <= i_start && j_start+1 <= j_end){ res.push("LR"); c = printShortestPath(n, i_start+2, j_start+1, i_end, j_end, res); }else{ return false; } } // if end is on bottom left, LL else if(i_end > i_start && j_end < j_start ) { //System.out.println("4 "); if(i_start+2 <= i_end && j_start-1>=0){ res.push("LL"); c = printShortestPath(n, i_start+2, j_start-1, i_end, j_end,res); }else{ return false; } }else{ return false; } if(c) return true; else return false; } 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. // impossible situation /* // if exactly on left or right if(i_start == i_end){ System.out.println("0 "); if(Math.abs(j_start-j_end) %2 == 1){ // impossible System.out.print("Impossible"); } else if(j_end < j_start){ System.out.print("L "); printShortestPath(n, i_start, j_start-2, i_end, j_end); } else if(j_end > j_start){ System.out.print("R "); printShortestPath(n, i_start, j_start+2, i_end, j_end); }else{ // complete. System.out.print("Complete."); } } // if end is on top left, UL // or // if end is on top exactly, UL else if(i_end < i_start && j_end <= j_start ) { // the next step is still in the board System.out.println("1 "); if(i_start-2 >= 0 && j_start-1>=0 ){ System.out.print("UL "); printShortestPath(n, i_start-2, j_start-1, i_end, j_end); }else{ System.out.print("Impossible "); } } // if end is on top right, UR // or // (if end is on right exactly, UR ) else if(i_end < i_start && j_end > j_start ) { System.out.println("2 "); if(i_start-2 >= 0 && j_start+1 <= j_end ){ System.out.print("UR "); printShortestPath(n, i_start-2, j_start+1, i_end, j_end); }else{ System.out.print("Impossible "); } } // if end is on bottom right, LR // or // if end is on bottom exactly,LR else if( i_end > i_start && j_end >= j_start ) { System.out.println("3 "); if(i_start+2 <= i_start && j_start+1 <= j_end){ System.out.print("LR "); printShortestPath(n, i_start+2, j_start+1, i_end, j_end); }else{ System.out.print("Impossible "); } } // if end is on bottom left, LL // or // (if end is on left exactly, LL) else if(i_end > i_start && j_end < j_start ) { System.out.println("4 "); if(i_start+2 =0){ System.out.print("LL "); printShortestPath(n, i_start+2, j_start-1, i_end, j_end); }else{ System.out.print("Impossible "); } } else{ System.out.print("Impossible"); } */ Stack res = new Stack(); int count = 0; boolean ck = printShortestPath(n, i_start, j_start, i_end, j_end, res); if(!ck){ System.out.print("Impossible"); }else{ // System.out.println(res.pop()); StringBuilder sb = new StringBuilder(); while(!res.isEmpty()){ sb.insert(0, res.pop()+" "); count++; } System.out.println(count); System.out.print(sb.toString()); } } 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(); } }