Task:
You are given a chessboard of n rows and m columns. There’s an integer number on each cell of the board and the knight staying in cell (x1, y1). He wants to reach the cell (x2, y2) where tasty grass grows.
What’s the minimal number of steps he has to do to reach the cell?
The knight can go in 8 directions.
Input:
The first line contains two naturals n and m – the quantity of rows and columns of the chessboard (2 ≤ n, m ≤ 20).
The second line contains coordinates (x1, y1) of the cell the knight stands in (1 ≤ x1 ≤ n, 1 ≤ y1 ≤ m).
The third line contains coordinates (x2, y2) of the cell the knight needs to reach (1 ≤ x2 ≤ n, 1 ≤ y2 ≤ m).
The upper-left corner’s coordinates are (1, 1), the lower-right corner’s – (n, m).
Output:
The first line should contain the minimal number of steps k.
The next k+1 lines should contain two numbers – coordinates of knight’s next cell to move to (the first of them must be the cell (x1, y1)).
If it’s impossible to reach (x2, y2), write -1.
Example:
|
Input |
Output |
|
5 5 3 3 5 1 |
4 3 3 2 1 1 3 3 2 5 1 |