import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static int range =0; static Pos[][] chessboard; static Queue q = new LinkedList(); static void printShortestPath(int range, int i_start, int j_start, int i_end, int j_end) { chessboard = new Pos[range][range]; populateChessBoard(); Pos start = new Pos(i_start, j_start, 0); Pos end = new Pos(i_end, j_end, Integer.MAX_VALUE); Pos prevPos = start; chessboard[0][1] = new Pos(start.x, start.y, 0); q.add(start); while (q.size() != 0) { Pos pos = q.poll(); if (end.equals(pos)) { Iterable path = getShortestPath(start, end); System.out.println(pos.depth); for(Pos position: path) { int deltaR = prevPos.x - position.x; int deltaC = prevPos.y - position.y; if(deltaR ==-2 && deltaC == 0) System.out.print("L "); else if(deltaR==-1 && deltaC ==2) System.out.print("LL "); else if(deltaR==-1 && deltaC ==-2) System.out.print("UL "); else if(deltaR==1 && deltaC ==-2) System.out.print("LR "); else if(deltaR==1 && deltaC ==2) System.out.print("UR "); else if(deltaR==2 && deltaC ==0) System.out.print("R "); else System.out.print("UL "); prevPos = position; } return; } else { bfs(pos, ++pos.depth); } } System.out.println("Impossible"); } private static void bfs(Pos current, int depth) { for (int i = -2; i <= 2; i++) { for (int j = -2; j <= 2; j+=2) { Pos next = new Pos(current.x + i, current.y + j, depth); if(inRange(next.x, next.y, range)) { if(current.equals(next)) continue; if (isValid(current, next)) { Pos position = chessboard[next.x][next.y] ; if (position.depth > depth) { chessboard[current.x + i][current.y + j] = new Pos(current.x, current.y, depth); q.add(next); } } } } } } private static boolean inRange(int x, int y,int range) { return 0 <= x && x < range && 0 <= y && y < range; } public static boolean isValid(Pos current, Pos next) { int deltaR = next.x - current.x; int deltaC = next.y - current.y; if(deltaR ==-2 && deltaC == 0){ return true; } else if(deltaR==-1 && deltaC ==2){ return true;} else if(deltaR==-1 && deltaC ==-2){ return true;} else if(deltaR==1 && deltaC ==-2){ return true;} else if(deltaR==1 && deltaC ==2) { return true;} else if(deltaR==2 && deltaC ==0) { return true;} else return false; } private static void populateChessBoard() { for (int i = 0; i < chessboard.length; i++) { for (int j = 0; j < chessboard[0].length; j++) { chessboard[i][j] = new Pos(Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE); } } } private static Iterable getShortestPath(Pos start, Pos end) { Stack path = new Stack(); Pos current = chessboard[end.x][end.y]; while(! current.equals(start)) { path.add(current); current = chessboard[current.x][current.y]; } path.add(new Solution.Pos(start.x, start.y, 0)); return path; } public static void main(String[] args) { Scanner in = new Scanner(System.in); range = in.nextInt(); int j_start = in.nextInt(); int i_start = in.nextInt(); int j_end = in.nextInt(); int i_end = in.nextInt(); printShortestPath(range, i_start, j_start, i_end, j_end); in.close(); } static class Pos { public int x; public int y; public int depth; Pos(int x, int y, int depth) { this.x = x; this.y = y; this.depth = depth; } public boolean equals(Pos that) { return this.x == that.x && this.y == that.y; } } }