import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { 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[] loc = {i_start - i_end, j_start - j_end}; int x = i_start, y = j_start; int z = 0; int UL=0, UR=0, L=0, R=0, LL=0, LR = 0; boolean routeFound = false; // Special Case 1 if(j_start == j_end && Math.abs(i_start-i_end) > 3 && Math.abs(i_start-i_end)%4 == 0) { if(i_start < i_end) { System.out.println((i_end-i_start)/2); for(int i=0; i<(i_end-i_start)/2-1; i++) System.out.print("LR "); for(int j=0; j<(i_end-i_start)/2-1; j++) System.out.print("LL "); } else { System.out.println((i_start-i_end)/2); for(int i=0; i<(i_start-i_end)/2-1; i++) System.out.print("UL "); for(int j=0; j<(i_start-i_end)/2-1; j++) System.out.print("UR "); } } // Special Case 2 else if(i_start == i_end && Math.abs(j_start-j_end)%2 == 0) { System.out.println(Math.abs(j_start-j_end)/2); if(j_start < j_end) { for(int i=0; i<(j_end-j_start)/2; i++) System.out.print("R "); } else { for(int j=0; j<(j_start-j_end)/2; j++) System.out.print("L "); } } else if(Math.abs(i_start-i_end)%2 == 1) System.out.print("Impossible"); else if(Math.abs((i_start-i_end)/2)%2 == 1 && Math.abs(j_start-j_end)%2 == 0) System.out.print("Impossible"); else if(Math.abs((i_start-i_end)/2)%2 == 0 && Math.abs(j_start-j_end)%2 == 1) System.out.print("Impossible"); // Area 1 else if(loc[0] > 0 && loc[1] > 0) { x = (i_start - i_end)/2; y = y - x; while(y >= j_end) { if(y == j_end) { routeFound = true; break; } y = y - 2; L++; } if(!routeFound) { y = j_start - x; while(y < j_start) { y = y + 2; R++; x--; if(y == j_end) { routeFound = true; break; } } } if(routeFound) { if(R != 0) { System.out.println(x+R); for(int i=0; i 0) { x = (i_end-i_start)/2; y = y - x; while(y >= j_end) { if(y == j_end) { routeFound = true; break; } y = y - 2; L++; } if(!routeFound) { y = j_start - x; while(y < j_start) { y = y + 2; R++; x--; if(y == j_end) { routeFound = true; break; } } } if(routeFound) { if(R != 0) { System.out.println(x+R); for(int i=0; i 0 && loc[1] < 0) { x = (i_start-i_end)/2; y = y + x; while(y <= j_end) { if(y == j_end) { routeFound = true; break; } y = y + 2; R++; } if(!routeFound) { y = j_start + x; while(y > j_start) { y = y - 2; L++; x--; if(y == j_end) { routeFound = true; break; } } } if(routeFound) { if(L != 0) { System.out.println(x+L); for(int i=0; i= 0 && y+1 <= j_end) { x = x-2; y = y+1; UR++; if(x == i_end && y == j_end) { routeFound = true; break; } } if(!routeFound) { while(x < i_start && y <= j_end) { z = y; while(z >= 0) { z = z+2; R++; if(x == i_end && z == j_end) { routeFound = true; break; } } if(routeFound) break; else { x = x+2; y = y-1; UR--; R = 0; } } } if(routeFound) { System.out.println(UL+L); for(int i=0; i j_start) { y = y - 2; L++; x--; if(y == j_end) { routeFound = true; break; } } } if(routeFound) { if(L != 0) { System.out.println(x+L); for(int i=0; i= i_start && y <= j_end) { z = y; while(z >= 0) { z = z+2; R++; if(x == i_end && z == j_end) { routeFound = true; break; } } if(routeFound) break; else { x = x-2; y = y-1; LR--; R = 0; } } } if(routeFound) { System.out.println(LR+R); for(int i=0; i