P7630 [COCI 2011/2012 #1] SKAKAC

Mirko and Slavko are playing a game. Mirko places a knight piece on an $N \times N$ chessboard, covers Slavko's eyes, and then moves the knight for $T$ steps, one move per second. After that, Slavko must guess the knight's final position to win. The chessboard in this game is special, because each square is forbidden for part of the time. More precisely, each square has a positive integer label. A square labeled with the number $K$ is passable only at times $0, K, K \times 2, K \times 3, ...$ seconds, and at all other times this square is forbidden. Of course, the knight may enter a square only when that square is passable. The game starts at time $0$. Every second, Mirko must move the knight by one step (according to the rules of chess: the knight moves in an L-shape, like the horse in Chinese chess). Please help Slavko write a program to compute all squares where the knight may be located after $T$ seconds.

The first line contains two positive integers $N, T$. The second line contains two positive integers $X, Y$, representing the knight's initial coordinates. The next $N$ lines each contain $N$ positive integers not exceeding $10^9$, describing the chessboard.

The first line contains a non-negative integer $M$, the number of squares where the knight may be located after $T$ seconds. The next $M$ lines each contain one coordinate, indicating a square where the knight may be located after $T$ seconds. Output the coordinates sorted by increasing row number, and if the row numbers are the same, by increasing column number.

#### Sample 1 Explanation The state of the chessboard is shown in the figure below. `.` represents a passable square, `#` represents a forbidden square, and `K` represents a square where the knight may be located.  #### Constraints For $40\%$ of the testdata, $T \le 5 \times 10^4$. For $100\%$ of the testdata, $3 \le N \le 30$, $1 \le T \le 10^6$. #### Notes The score of this problem follows the original COCI settings, with a full score of $160$. Translated from **[COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #1](https://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf)** ___T6 SKAKAC___. Translated by ChatGPT 5