import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static class Postion implements Comparable{ int row; int col; List path_to = null; private Postion(int row, int col) { super(); this.row = row; this.col = col; } @Override public int compareTo(Postion o) { int n1, n2; n1 = (this.path_to == null) ? Integer.MAX_VALUE : this.path_to.size(); n2 = (o.path_to == null) ? Integer.MAX_VALUE : o.path_to.size(); if(n1 == n2 && n1 != Integer.MAX_VALUE){ for(int i = 0; i < n1 ;i++){ if( this.path_to.get(i) < o.path_to.get(i) ) return -1; if( this.path_to.get(i) > o.path_to.get(i) ) return 1; } return 0; } return n1 - n2; } @Override public String toString() { String tmp = (path_to == null) ? "[]" : Arrays.toString(path_to.toArray()); return "Postion [(" + row + ":" + col + ") , " + tmp + "]"; } } static int table_size; static String[] move_names = new String[]{"UL", "UR", "R", "LR", "LL", "L"}; static Postion getTargetPosition(Postion current_pos, int move){ Postion p = null; switch (move) { case 0: p = new Postion(current_pos.row - 2, current_pos.col -1); break; case 1: p = new Postion(current_pos.row - 2, current_pos.col +1); break; case 2: p = new Postion(current_pos.row, current_pos.col +2); break; case 3: p = new Postion(current_pos.row + 2, current_pos.col +1); break; case 4: p = new Postion(current_pos.row + 2, current_pos.col -1); break; case 5: p = new Postion(current_pos.row, current_pos.col -2); break; } if(p.row < 0 || p.row >= table_size || p.col < 0 || p.col >= table_size) return null; return p; } static List selectPath2(int n, int i_start, int j_start, int i_end, int j_end){ table_size = n; PriorityQueue next_positions = new PriorityQueue(); Postion[] lookup_table = new Postion[n*n]; Postion target = new Postion(i_start, j_start); target.path_to = Collections.emptyList(); next_positions.add(target); for(int x = 0 ; x < n ; x++){ for(int y = 0 ; y< n ; y++){ Postion p = new Postion(x, y); if( x != i_start || y != j_start){ next_positions.add(p); } lookup_table[x*n + y] = p; } } while(!next_positions.isEmpty()){ Postion cp = next_positions.remove(); if(cp.row == i_end && j_end == cp.col){ return cp.path_to; } if(cp.path_to == null) return null; for(int move = 0 ; move < move_names.length ; move++){ Postion p = getTargetPosition(cp, move); if(p != null){ //System.out.printf("DEBUG: %d:%d CURRENT NODE: %d:%d %s -> %d\n", p.row,p.col, cp.row, cp.col, Arrays.toString(cp.path_to.toArray()), move); List _path = new ArrayList<>(cp.path_to); _path.add(move); p.path_to = _path; Postion cached_p = lookup_table[p.row*n + p.col]; if(p.compareTo(cached_p) < 0){ next_positions.remove(cached_p); cached_p.path_to = _path; next_positions.add(cached_p); } } } } return null; } static List selectPath(int n, int i_start, int j_start, int i_end, int j_end){ if(i_start % 2 != i_end % 2){ return null; } ArrayList moves = new ArrayList(); int d_rows = i_start - i_end; int d_cols = j_start - j_end; while(d_rows != 0 || d_cols != 0){ //System.out.printf("%d:%d -> %d:%d \n",i_start, j_start, i_end,j_end); String c_move = null; // CHECK IF NEED TO MOVE DOWN if( d_rows > 0 ){ if(d_cols > 0){ c_move = "UL"; i_start -= 2; j_start -= 1; }else if(d_cols < 0){ c_move = "UR"; i_start -= 2; j_start += 1; }else{ // DAMM!! Heuristic no longer valid :( // I will just branch and select the best path latter. List path_R = selectPath(n, i_start-2, j_start-1, i_end, j_end); List path_L = selectPath(n, i_start-2, j_start+1, i_end, j_end); if( path_L.size() <= path_R.size() ){ moves.add("UL"); moves.addAll(path_L); }else{ moves.add("UR"); moves.addAll(path_R); } return moves; } } // THEN CHECK IF NEED TO MOVE RIGHT if( c_move == null && d_cols < 0 ){ c_move = "R"; j_start += 2; } // THEN CHECK IF NEED TO MOVE UP if( c_move == null && d_rows < 0 ){ if(d_cols < 0){ c_move = "LR"; i_start += 2; j_start += 1; }else if(d_cols > 0){ c_move = "LL"; i_start += 2; j_start -= 1; }else{ // DAMM!! Heuristic no longer valid :( // I will just branch and select the best path latter. List path_R = selectPath(n, i_start+2, j_start+1, i_end, j_end); List path_L = selectPath(n, i_start+2, j_start-1, i_end, j_end); if( path_R.size() <= path_L.size() ){ moves.add("LR"); moves.addAll(path_R); }else{ moves.add("LL"); moves.addAll(path_L); } return moves; } } // LASTLY MOVE LEFT IF POSSIBLE if( c_move == null && d_cols > 0 ){ c_move = "L"; j_start -= 2; } if(c_move != null){ moves.add(c_move); // UPDATE POSITION d_rows = i_start - i_end; d_cols = j_start - j_end; }else{ return null; } } return moves; } 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. List moves = selectPath2(n, i_start, j_start, i_end, j_end); if(moves == null) System.out.println("Impossible"); else{ System.out.println(moves.size()); for( int move : moves) System.out.print(move_names[move] + " "); } } 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(); } }