import java.io.PrintStream; import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Scanner; import java.util.Set; public class RedKnightsShortestPath { private enum DIR { UL(-1, -2), UR( 1, -2), R ( 2, 0), LR( 1, 2), LL(-1, 2), L (-2, 0); private final int dx; private final int dy; private DIR(int dx, int dy) { this.dx = dx; this.dy = dy; } public int getDx() { return dx; } public int getDy() { return dy; } } private static boolean between(int l, int v, int u) { return l <= v && v < u; } private boolean validPoint(int x, int y) { return between(0, x, width) && between(0, y, height); } private boolean validPoint(Point p) { return validPoint(p.getC(), p.getR()); } private class Point implements Comparable { private final int r; private final int c; public Point(int r, int c) { this.r = r; this.c = c; } public int getR() { return r; } public int getC() { return c; } public Point move(DIR d) { int newC = c + d.getDx(); int newR = r + d.getDy(); if (validPoint(newC, newR)) { return new Point(newR, newC); } else { return null; } } @Override public int compareTo(Point o) { if (r != o.r) { return Integer.valueOf(r).compareTo(o.r); } return Integer.valueOf(c).compareTo(o.c); } @Override public int hashCode() { int hash = 7; hash = 71 * hash + this.r; hash = 71 * hash + this.c; return hash; } @Override public boolean equals(Object obj) { if (this == obj) { return true; } if (obj == null) { return false; } if (getClass() != obj.getClass()) { return false; } final Point other = (Point) obj; if (this.r != other.r) { return false; } return this.c == other.c; } } private static class Path implements Comparable { private final List path; public Path(List path) { this.path = path; } public Path(Path oPath) { this(new ArrayList<>(oPath.path)); } public Path() { this(new ArrayList<>()); } public List getPath() { return path; } public int size() { return path.size(); } private void addToPath(DIR d) { path.add(d); } public Path extend(DIR d) { Path ans = new Path(this); ans.addToPath(d); return ans; } public void print(PrintStream out) { path.forEach((d) -> { out.printf("%s ", d.name()); }); } @Override public int compareTo(Object o) { if (o == this) { return 0; } if (o == null || !(o instanceof Path)) { return 1; } Path oPath = (Path)o; if (path.size() != oPath.size()) { return Integer.valueOf(path.size()).compareTo(oPath.size()); } Iterator iter = oPath.path.iterator(); for (DIR d : path) { DIR od = iter.next(); if (!d.equals(od)) { return d.compareTo(od); } } return 0; } } private final int width; private final int height; private final Path[][] board; private RedKnightsShortestPath(int width, int height) { this.width = width; this.height = height; this.board = new Path[height][width]; } private void clearBoard(int startX, int startY) { for (int x = 0 ; x < width ; ++x) { for (int y = 0 ; y < height ; ++y) { board[y][x] = null; } } board[startY][startX] = new Path(); } private Path getPathTo(int x, int y) { return board[y][x]; } private Path getPathTo(Point p) { return getPathTo(p.getC(), p.getR()); } private void setPathTo(Point p, Path path) { board[p.getR()][p.getC()] = path; } private Path solve(int startY, int startX, int endY, int endX) { clearBoard(startX, startY); Set curPoints = new HashSet<>(); curPoints.add(new Point(startY, startX)); while(!curPoints.isEmpty()) { Set newPoints = new HashSet<>(); for (Point p : curPoints) { Path curPath = getPathTo(p); for (DIR d : DIR.values()) { Point newP = p.move(d); if (newP != null) { Path newPath = curPath.extend(d); Path dPath = getPathTo(newP); if (dPath == null || newPath.compareTo(dPath) < 0) { setPathTo(newP, newPath); newPoints.add(newP); } } } } curPoints = newPoints; } return getPathTo(endX, endY); } static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { RedKnightsShortestPath solver = new RedKnightsShortestPath(n, n); Path path = solver.solve(i_start, j_start, i_end, j_end); if (path == null) { System.out.println("Impossible"); } else { System.out.println(path.size()); path.print(System.out); System.out.println(); } } public static void main(String[] args) { try (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); } } }