프로그램 명: coci_skakac
제한시간: 1.5 초

미코와 슬라브는 Knight 로 알려진 게임을 하고 있다. 슬라브코가 눈을 가린상태에서 ,미코가 knight 체스를 NxN 체스보드에 둔 후 초당 한 번씩 정확하게 T 번 움직인다. 그 후 슬라브코가 이기기 위해서 knight의 최종 위치를 추측해야 한다.

이 게임에서 체스보드는 보통하고는 틀려서 각 스퀘어는 시간대 별로 봉쇄된다.

더 정확하게 말하면 각 스퀘어는 양의 정수로 번호가 부여되어 있고 K 번호가 붙여진 스퀘어는 0 , K , 2K , 3K ... 동안만 사용가능하고 나머지 시간에는 봉쇄된다.

게임은 시각 0 초에 시작한다. 목적으로 하는 스퀘어가 다음 시간 동안 블록되지 않는다면 매 초별로 미코는 움직여야 한다. (움직임은 체스에서 knight 가 움직이는 규칙과 같다)

슬라브코를 도와 T 번 움직임 후에 knight 가 갈 수 있는 가능한 모든 스퀘어를 구하는 프로그램을 작성하라.

입력

출력

Mirko and Slavko are playing the popular new game known as The Knight. Mirko places a knight chess piece on an NxN 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 Lshaped 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.

입력

The first line of input contains two positive integers, N (3 ≤ N ≤ 30), the size of the chessboard, and T (1 ≤ T ≤ 1 000 000), the number of moves that Mirko will make. The second line of input contains two positive integers X and Y (1 ≤ X, Y ≤ 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.

입출력 예

input 

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

output 

2
1 1
1 3

input

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

output

5
1 4
2 1
2 5
4 5
5 2

input 

3 3 
2 2 
3 6 4  
2 2 5  
1 3 7  

output

0

SAMPLE TESTS

First sample description: 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’. 

출처:coci 2011 contest1  6/6
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]