Mirko and Slavko are playing the popular new game known as The Knight. Mirko places a knight chess piece on an chessboard and, with Slavko blindfolded, makes exactly moves, one per second. After that, Slavko must guess the final position of the knight in order to win.
The chessboard in this game is unusual in that each square is blocked part of the time. More precisely, each square is labelled by a positive integer. A square labelled by number is clear only during seconds etc; it is blocked at all other times. The knight can, of course, occupy a square only while the square is clear.
The game begins in second . In each second Mirko must make a move (selecting one of possible L-shaped moves, two squares in one direction and one square in the other, as per standard chess rules), provided that the destination square is not blocked during the next second. Help Slavko by writing a program to calculate all possible squares that the knight can possibly occupy after moves.
Input Specification
The first line of input contains two positive integers, , the size of the chessboard, and , the number of moves that Mirko will make.
The second line of input contains two positive integers and , the row and column indices of the knight's starting square selected by Mirko.
The next lines each contain positive integers less than (one billion), the values of for the corresponding chessboard squares.
Output Specification
The first line of output must contain the nonnegative integer , the number of squares that the knight can possibly occupy after moves.
The next lines must contain indices of those squares, sorted by increasing row index, with cells in the same row sorted by increasing column index.
Scoring
In test cases worth of total points, the number of moves will be less than .
Sample Input 1
3 2
1 1
1 3 2
2 3 2
3 1 1
Sample Output 1
2
1 1
1 3
Explanation for Sample Output 1
The state of the chessboard in each second is shown below. Clear cells are
denoted by .
, blocked cells by #
, and possible locations of the knight by K
.
second | second | second |
---|---|---|
K.. ... ... |
.## ### #K. |
K#K .#. #.. |
Sample Input 2
5 6
2 3
4 5 3 2 3
1 3 4 3 1
3 4 1 3 2
4 4 2 1 3
4 6 4 9 2
Sample Output 2
5
1 4
2 1
2 5
4 5
5 2
Sample Input 3
3 3
2 2
3 6 4
2 2 5
1 3 7
Sample Output 3
0
Comments