import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Collection; import java.util.Deque; import java.io.InputStreamReader; import java.util.Queue; import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayDeque; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top * * @author Maxim Paliy */ public class Solution { public static void main(String[] args) throws Exception { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputParser in = new InputParser(inputStream); PrintWriter out = new PrintWriter(outputStream); RedKnightsShortestPath solver = new RedKnightsShortestPath(); solver.solve(1, in, out); out.close(); } static class RedKnightsShortestPath { public static final String IMPOSSIBLE = "Impossible"; public void solve(int testNumber, InputParser in, PrintWriter out) throws Exception { int n = in.readInt(); int[] arr = in.readArrayOfInts(4, false); int xStart = arr[1]; int yStart = arr[0]; int xEnd = arr[3]; int yEnd = arr[2]; if ((yEnd - yStart) % 2 != 0) { out.println(IMPOSSIBLE); return; } else if (((yEnd - yStart) % 4 == 0) && ((xEnd - xStart) % 2 != 0)) { out.println(IMPOSSIBLE); return; } else if (((yEnd - yStart) % 4 == 2) && ((xEnd - xStart) % 2 != 1)) { out.println(IMPOSSIBLE); return; } boolean[][] visited = new boolean[n][n]; visited[xStart][yStart] = true; Queue bfs = new ArrayDeque<>(); bfs.add(new RedKnightsShortestPath.Position(xStart, yStart, null, null)); while (!bfs.isEmpty()) { RedKnightsShortestPath.Position currentPosition = bfs.poll(); if ((currentPosition.x == xEnd) && (currentPosition.y == yEnd)) { Deque path = new ArrayDeque<>(); while (currentPosition.previousMove != null) { path.addFirst(currentPosition.previousMove); currentPosition = currentPosition.previousPosition; } out.println(path.size()); StringBuilder stringBuilder = new StringBuilder(); for (RedKnightsShortestPath.Direction direction : path) { stringBuilder.append(direction).append(" "); } out.println(stringBuilder.toString()); return; } for (RedKnightsShortestPath.Direction direction : RedKnightsShortestPath.Direction.values()) { int newX = currentPosition.x + direction.diffX; int newY = currentPosition.y + direction.diffY; if ((newX >= 0) && (newX < n) && (newY >= 0) && (newY < n) && (!visited[newX][newY])) { bfs.add(new RedKnightsShortestPath.Position(newX, newY, direction, currentPosition)); visited[newX][newY] = true; } } } } enum Direction { UL(-1, -2), UR(1, -2), R(2, 0), LR(1, 2), LL(-1,2), L(-2, 0); int diffX; int diffY; Direction(int diffX, int diffY) { this.diffX = diffX; this.diffY = diffY; } } static class Position { int x; int y; RedKnightsShortestPath.Direction previousMove; RedKnightsShortestPath.Position previousPosition; public Position(int x, int y, RedKnightsShortestPath.Direction previousMove, RedKnightsShortestPath.Position previousPosition) { this.x = x; this.y = y; this.previousMove = previousMove; this.previousPosition = previousPosition; } } } static class InputParser { BufferedReader bufferedReader; public InputParser(Class klazz, int caseNumber) throws Exception { this("src/main/cases/" + klazz.getSimpleName() + "/" + caseNumber); } public InputParser() { this(System.in); } public InputParser(String fileName) throws Exception { bufferedReader = new BufferedReader(new FileReader(fileName)); } public InputParser(InputStream in) { bufferedReader = new BufferedReader(new InputStreamReader(in)); } public int[] readArrayOfInts(int size, boolean decreaseByOne) throws Exception { int[] result = new int[size]; String line = bufferedReader.readLine(); int lastSpacePos = 0; for (int j = 0; j < size; j++) { int spacePos = line.indexOf(' ', lastSpacePos); if (spacePos < 0) { spacePos = line.length(); } int value = Integer.parseInt(line.substring(lastSpacePos, spacePos)) - (decreaseByOne ? 1 : 0); result[j] = value; lastSpacePos = spacePos + 1; } return result; } public int readInt() throws Exception { return Integer.parseInt(bufferedReader.readLine()); } } }