import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { static class Position { public enum Move { UL(-1, -2), UR(1, -2), R(2, 0), LR(1, 2), LL(-1, 2), L(-2, 0); private final int x; private final int y; Move(int x, int y) { this.x = x; this.y = y; } } private int x; private int y; public Position(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object obj) { if (obj instanceof Position) { Position other = ((Position) obj); return other.x == this.x && other.y == this.y; } return false; } public Position minus(Position other) { return new Position(this.x - other.x, this.y - other.y); } private double distanceWithMove(Position end, Move move) { return new Position(x, y).translate(move).minus(end).norm(); } public double norm() { return Math.sqrt(x * x + y * y); } public void translate(int xDiff, int yDiff) { x += xDiff; y += yDiff; } public Position translate(Move move) { translate(move.x, move.y); return this; } // 9, 8, 11 public Move getPrioritizedMoveTo(Position end, int n) { int xd = end.x - x; int yd = end.y - y; if (xd <= 0 && yd < 0 && onBoard(Move.UL, n)) { return Move.UL; } if (xd >= 0 && yd < 0 && onBoard(Move.UR, n)) { return Move.UR; } if (xd > 0 && yd == 0 && onBoard(Move.R, n)) { return Move.R; } if (xd >= 0 && yd > 0 && onBoard(Move.LR, n)) { return Move.LR; } if (xd <= 0 && yd > 0 && onBoard(Move.LL, n)) { return Move.LL; } if (xd < 0 && yd == 0 && onBoard(Move.L, n)) { return Move.L; } throw new IllegalStateException("cant reach position!"); } private boolean onBoard(Move move, int n) { Position afterMove = new Position(x, y).translate(move); return onBoard(afterMove, n); } public static boolean onBoard(Position afterMove, int n) { return afterMove.x >= 0 && afterMove.y >= 0 && afterMove.x < n && afterMove.y < n; } public Move getShortestMoveTo(Position end, int n) { Move[] moves = Arrays.asList(Move.L, Move.LL, Move.LR, Move.R, Move.UR, Move.UL).toArray(new Move[6]); Double[] simulation = Arrays.asList( distanceWithMove(end, Move.L), distanceWithMove(end, Move.LL), distanceWithMove(end, Move.LR), distanceWithMove(end, Move.R), distanceWithMove(end, Move.UR), distanceWithMove(end, Move.UL)).toArray(new Double[1]); // which move brings us faster to the end? int best = -1; double distance = Double.MAX_VALUE; for (int i = 0; i < 6; i++) { if (simulation[i] <= distance) { best = i; distance = simulation[i]; } } return moves[best]; } } // 9 8 11 static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { Position current = new Position(j_start, i_start); Position end = new Position(j_end, i_end); List path = new ArrayList<>(); try { if (!Position.onBoard(current, n) && Position.onBoard(end, n)) { throw new IllegalArgumentException("wrong input"); } double distance = Double.MAX_VALUE; while (!current.equals(end)) { Position diff = end.minus(current); if (diff.norm() >= distance) { throw new IllegalArgumentException("distance cant increase!"); } distance = diff.norm(); Position.Move move = current.getPrioritizedMoveTo(end, n); path.add(move); current.translate(move); } // so now we knew a path, but is it the shortest? // we test if there ist a not order prior try { List shorterPath = new ArrayList<>(); distance = Double.MAX_VALUE; current = new Position(j_start, i_start); while (!current.equals(end)) { Position diff = end.minus(current); if (diff.norm() >= distance) { throw new IllegalArgumentException("distance cant increase!"); } distance = diff.norm(); Position.Move move = current.getShortestMoveTo(end, n); shorterPath.add(move); current.translate(move); } if (shorterPath.size() < path.size()) { path = shorterPath; } } catch (RuntimeException ex) { //ex.printStackTrace(); } path.sort(Comparator.comparingInt(Enum::ordinal)); StringBuilder sb = new StringBuilder(); for (Position.Move m : path) { sb.append(m.name() + " "); } System.out.println(path.size()); System.out.println(sb.toString().trim()); } catch (RuntimeException ex) { 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(); } }