Hryhorii the Grasshopper#4155
Hryhorii is a grasshopper. His favourite food is clover leaves — he never gets enough of them. Whenever he sees such a leaf, he wants to eat it as quickly as possible. But Hryhorii is also lazy, so he wants to reach the leaf with minimal effort. Your task is to help him find the shortest path to the clover leaf.
For simplicity, assume that Hryhorii lives on a rectangular grid of unit squares. As a grasshopper, he moves by hopping from one square to another. Each hop takes him to a square that is next to the current one in row or column in one direction, and two columns or rows away in the other direction. Thus, his hops resemble the moves of a knight on a chessboard.
The input consists of several test cases, each given by six integer numbers in one line: , , , , , and . and specify the size of the grid in unit squares, 1 \le R, C \le 100. Hryhorii cannot hop outside a rectangle of this size, because it would be too dangerous. The values of , are the coordinates of the square where Hryhorii is standing, and , are the coordinates of the square with the delicious clover leaf. (1 \le GR, LR \le R, 1 \le GC, LC \le C)
For each test case, output one integer — the minimal number of hops that Hryhorii needs to reach the square with his favourite delicacy. If it is impossible to reach that square, print "impossible" instead.
Example 1