Gregory the Grasshopper

Time limit1sMemory limit128 MB

Summary

Find the fewest knight moves from one square to another on a grid of up to 100 by 100, or report that it is impossible.

Level: Medium4 of 10
Topics: BFS, Graph, Shortest path
Solved: No attempts yet

Problem

Gregory is a grasshopper. His favourite food is clover leaves — he can simply never have enough of them. Whenever he spots such a leaf, he wants to eat it as quickly as possible. Gregory is also lazy, so he wants to reach the leaf with the least possible effort. Your task is to help him find the shortest way to a clover leaf.

For simplicity, we assume that Gregory lives on a rectangular grid made of unit squares. As a grasshopper, he prefers to move by hopping from one square to another. Each hop takes him to a square that is one row (or column) away in one direction and two columns (or rows) away in the other direction. In other words, his hops are exactly the moves of a knight on a chessboard.

Input

The input consists of several test cases. Each test case is given on one line as six integers $R$ , $C$ , $GR$ , $GC$ , $LR$ , $LC$ . $R$ and $C$ are the size of the grid in unit squares, with $1 \le R, C \le 100$ . Gregory may not hop outside this rectangle, because it would be too dangerous. $GR$ , $GC$ are the coordinates of the square Gregory is standing on, and $LR$ , $LC$ are the coordinates of the square with the delicious clover leaf ( $1 \le GR, LR \le R$ ; $1 \le GC, LC \le C$ ). The input continues until the end of file.

Output

For each test case, print one integer — the minimum number of hops Gregory needs to reach the square with his beloved delicacy. If that square cannot be reached at all, print the word impossible instead.

Examples1

Example 1

Input

10 10 10 10 1 1
2 2 1 1 1 2
8 8 1 1 1 2

Expected output

6
impossible
3