import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { /* while (not reached end or impossible) { 1 generate prioritized list of moves 2 explore graph } 3 output result or Impossible */ enum Move { UL(+2, -1), UR(+2, +1), R(0, +2), LR(-2, +1), LL(-2, -1), L(0, -2); public final int horizDist; public final int vertDist; Move(int i, int j) { vertDist = i; horizDist = j; } @Override public String toString() { return this.name(); } } 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. Coord start = flipVertical(new Coord(i_start, j_start)); Coord end = flipVertical(new Coord(i_end, j_end)); findPath(n, start, end); } static String findPath(int boardSize, Coord start, Coord end) { Queue queue = new PriorityQueue<>(); List visited = new ArrayList<>(); Coord goal = findPathAStar(queue, visited, boardSize, start, end); if (goal == null) { System.out.println("Impossible"); return "Impossible"; } else { Coord curr = goal; Deque moves = new ArrayDeque<>(); while(curr.prev != null) { moves.addFirst(curr.move); curr = curr.prev; } StringBuilder str = new StringBuilder(); for(Move m : moves) { str.append(m.name()); str.append(" "); } System.out.println(moves.size()); String path = str.toString().trim(); System.out.println(path); return path; } } private static boolean findPathBFS(Queue queue, List visited, int boardSize, Coord start, Coord end) { queue.add(start); while (!queue.isEmpty()) { Coord curr = queue.poll(); visited.add(curr); if (curr.equals(end)) { return true; } else { Map moves = generateMoves(boardSize, curr); for(Coord c : moves.values()) { if (!visited.contains(c)) { queue.add(c); } } } } return false; } private static Coord findPathAStar(Queue queue, List visited, int boardSize, Coord start, Coord end) { Coord scoredStart = new Coord(start); scoredStart.g = 0d; queue.add(scoredStart); while (!queue.isEmpty()) { Coord curr = queue.poll(); visited.add(curr); if (curr.i == end.i && curr.j == end.j) { return curr; } else { Map moves = generateMoves(boardSize, curr); for(Move m: moves.keySet()) { if (!visited.contains(moves.get(m))) { queue.add(scoreAStar(curr, moves.get(m), end, m)); } } } } return null; } static Coord scoreAStar(Coord from, Coord to, Coord goal, Move move) { Coord scored = new Coord(to.i, to.j); scored.g = from.g + dist(from, to); scored.f = scored.g + dist(to, goal); scored.move = move; scored.prev = from; return scored; } static double dist(Coord from, Coord to) { return Math.pow(from.i - to.i, 2) + Math.pow(from.j - to.j, 2); } private static Coord flipVertical(Coord c) { return new Coord(-c.i, c.j); } static Map generateMoves(int boardSize, Coord from) { Map moves = new TreeMap<>(); for (Move move : Move.values()) { Coord next = move(move, from); if (insideGrid(boardSize, next)) { moves.put(move, next); } } return moves; } static Coord move(Move move, Coord from) { return new Coord( from.i + move.vertDist, from.j + move.horizDist ); } static boolean insideGrid(int boardSize, Coord to) { return (0 >= to.i && to.i > -boardSize) && (0 <= to.j && to.j < boardSize); } static class Coord implements Comparable{ public final int i; public final int j; public Double g; public Double f; public Move move; public Coord prev; Coord(int i, int j) { this.i = i; this.j = j; } public Coord(Coord other) { this.i = other.i; this.j = other.j; } @Override public int compareTo(Object o) { Coord other = (Coord) o; Double diff = this.f - other.f; return diff == 0d ? 0 : (diff > 0 ? 1 : -1); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Coord coord = (Coord) o; if (i != coord.i) return false; return j == coord.j; } @Override public int hashCode() { int result = i; result = 31 * result + j; return result; } @Override public String toString() { return "Coord{" + "i=" + i + ", j=" + j + ", prev=" + prev + '}'; } } 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(); } }