import java.util.ArrayList; 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) { DifferentGraph g = new DifferentGraph(n, i_start, j_start, i_end, j_end); MST mst = new MST(g); Point pEnd = new Point(i_end, j_end); if (mst.hasPathTo(pEnd)) { System.out.println(mst.distTo(pEnd)); mst.pathTo(pEnd); } else { System.out.println("Impossible"); } } 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(); } } class MST { boolean[][] visited; int[][] distTo; Point[][] edgeTo; Queue q = new LinkedList(); DifferentGraph g; MST(DifferentGraph g){ this.g= g; visited = new boolean[g.n][g.n]; distTo = new int[g.n][g.n]; edgeTo = new Point[g.n][g.n]; for (int i = 0; i < g.n; i++) { for (int j = 0; j < g.n; j++) { distTo[i][j] = Integer.MAX_VALUE; } } distTo[g.start.x][g.start.y] = 0; q.add(g.start); visited[g.start.x][g.start.y] = true; while (!q.isEmpty()) { relax(q.remove()); } } private void relax(Point pFrom) { for(Point pTo : g.adj(pFrom)) { if (!isVisited(pTo)) { relax(pFrom,pTo); } } } private boolean isVisited(Point p) { return visited[p.x][p.y]; } private void relax(Point pFrom, Point pTo) { if (distTo[pTo.x][pTo.y] > distTo[pFrom.x][pFrom.y] + 1) { distTo[pTo.x][pTo.y] = distTo[pFrom.x][pFrom.y]+ 1; edgeTo[pTo.x][pTo.y] = pFrom; } visited[pTo.x][pTo.y] = true; q.add(pTo); } boolean hasPathTo(Point p) { return visited[p.x][p.y]; } int distTo(Point p) { return distTo[p.x][p.y]; } void pathTo(Point pEnd) { Stack st = new Stack(); Point p = pEnd; while (!p.equals(g.start)) { st.push(p); p = edgeTo[p.x][p.y]; } p = g.start; while (!st.isEmpty()) { Point pTo = st.pop(); System.out.print(print(p, pTo) + " "); p = pTo; } } private String print(Point p, Point pTo) { int xDiff = pTo.x - p.x; int yDiff = pTo.y - p.y; if (xDiff == -2) { if (yDiff == -1) return "UL"; if (yDiff == +1) return "UR"; } if (xDiff == 0) { if (yDiff == -2) return "L"; if (yDiff == 2) return "R"; } if (xDiff == 2) { if (yDiff == -1) return "LL"; if (yDiff == +1) return "LR"; } return ""; } } class DifferentGraph { Point start; Point end; int n; DifferentGraph(int n, int i_start, int j_start, int i_end, int j_end) { this.n= n; start = new Point (i_start, j_start); end = new Point(i_end, j_end); } public Iterable adj(Point p) { boolean[] ok = new boolean[6]; ArrayList al = new ArrayList(); int x = p.x; int y = p.y; if (y - 1 >=0) { if (x - 2 >=0) ok[0]=true; // UL if (x+2 < n) ok[4]=true; ; // LL if (y - 2 >= 0) { ok[5] = true; // L } } if (y+1 < n) { if (x-2 >=0) ok[1]=true; // UR if (x+2 < n) ok[3] = true; // LR if (y + 2 < n) { ok[2] = true; // R } } if (ok[0]) al.add(new Point(x-2,y-1)); if (ok[1]) al.add(new Point(x-2,y+1)); if (ok[2]) al.add(new Point(x,y + 2)); if (ok[3]) al.add(new Point(x+2,y+1)); if (ok[4]) al.add(new Point(x+2,y-1)); if (ok[5]) al.add(new Point(x,y-2)); return al; } } class Point { @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + x; result = prime * result + y; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Point other = (Point) obj; if (x != other.x) return false; if (y != other.y) return false; return true; } @Override public String toString() { return "Point [x=" + x + ", y=" + y + "]"; } int x; int y; Point(int x, int y){ this.x = x; this.y = y; } }