Problem Description

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 $T$ steps, one step per second. Slavko must guess the final position of the knight to win.

The chessboard in this game is special because each square has a portion of time when it is forbidden to pass through. More precisely, each square is marked with a positive integer $K$, and the square with the number $K$ is only allowed to be passed through at times $0, K, K \times 2, K \times 3, ...$ seconds. At other times, the square is forbidden. Of course, the knight can only move to a square when it is allowed to pass through.

The game starts at time $0$ seconds. Each second, Mirko must move the knight one step (according to the rules of chess, the knight moves in an "L" shape, similar to the horse in Chinese chess). Help Slavko write a program to calculate all the squares the knight could be on after $T$ seconds.

Input Format

The first line of input contains two positive integers $N, T$.

The second line contains two positive integers $X, Y$, representing the initial coordinates of the knight.

The next $N$ lines each contain $N$ positive integers not exceeding $10^9$, describing the chessboard.

Output Format

The first line of output is a non-negative integer $M$, indicating the number of squares the knight could be on after $T$ seconds.

The next $M$ lines each contain a coordinate, indicating the squares the knight could be on after $T$ seconds. The coordinates should be sorted by row number in ascending order, and if the row numbers are the same, by column number in ascending order.

Sample Input and Output

Sample Input #1

3 2
1 1
1 3 2
2 3 2
3 1 1

Sample Output #1

2
1 1
1 3

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

Notes

Sample 1 Explanation

The state of the chessboard is shown in the diagram below. . represents an allowed square, # represents a forbidden square, and K represents a possible position of the knight.

Data Range

For $40\%$ of the data, $T \le 5 \times 10^4$.

For $100\%$ of the data, $3 \le N \le 30$, $1 \le T \le 10^6$.

Notes

This problem is scored according to the original COCI settings, with a full score of $160$.

The problem is translated from COCI2011-2012 CONTEST #1 T6 SKAKAC.

见题面 Input 部分

见题面 Output 部分