Mirko and Slavko are playing the popular new game known as The Knight. Mirko places a knight chess piece on an \(N \times N\) chessboard and, with Slavko blindfolded, makes exactly \(T\) 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 \(K\) is clear only during seconds \(0, K, 2K, 3K\) 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 \(0\). In each second Mirko must make a move (selecting one of \(8\) 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 \(T\) moves.

In test cases worth 40% of total points, the number of moves T will be less than 50 000.
\(1^{st}\) round, October \(22^{nd}\), 2011

The first line of input contains two positive integers, \(N\) (\(3 \le N \le 30\)), the size of the chessboard, and \(T\) (\(1 \le T \le 1\,000\,000\)), the number of moves that Mirko will make.

The second line of input contains two positive integers \(X\) and \(Y\) (\(1 \le X, Y \le N\)), the row and column indices of the knight's starting square selected by Mirko.

The next \(N\) lines each contain \(N\) positive integers less than \(10^9\) (one billion), the values of \(K\) for the corresponding chessboard squares.

The first line of output must contain the nonnegative integer \(M\), the number of squares that the knight can possibly occupy after \(T\) moves.

The next \(M\) 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 \(40\%\) of total points, the number of moves \(T\) will be less than \(50\,000\).

riseoj 작성

출처 COCI 2011/2012 Contest 1