(p, q) - horse#2402
-horse is a generalization of the standard chess knight. A -horse moves by cells in one direction and cells in the other (perpendicular) direction. For example, a -horse can move from cell to cells , , , , , , , and . Obviously, a standard chess knight is a -horse.
Your task is to determine the minimum number of moves needed for a -horse to get from one cell of an M \times N chessboard to another. Leaving the board is not allowed.
The input contains a single line with integers: , , , , x_1, y_1, x_2, y_2 (1 \leq x_1, x_2 \leq M \leq 100, 1 \leq y_1, y_2 \leq N \leq 100, 0 \leq p \leq 100, 0 \leq q \leq 100).
The first line should contain an integer — the number of moves the -horse needs to move from cell (x_1, y_1) to cell (x_2, y_2). Then print k+1 lines with the consecutive positions of the -horse along this path.
If the -horse cannot reach (x_2, y_2) from (x_1, y_1), output a single number .
Example 1
Example 2