옥수수밭

문제

옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 $N$행 $M$열의 격자로 생각할 수 있는데, 격자의 각 칸에는 한 그루의 옥수수가 심어져 있다. 민석이는 각 옥수수의 가치를 측정해서 서로 다른 정수 $1, 2, \cdots, N \times M$을 부여했다.

민석이는 처음에 옥수수밭 바깥에 위치한다. 민석이는 옥수수밭 바깥을 돌아다니면서 옥수수밭 바깥과 인접한 칸의 옥수수를 수확할 수 있다. 또는 옥수수밭 안에서 옥수수를 수확한 칸으로만 돌아다니면서 현재 위치한 칸에서 상하좌우로 인접한 칸의 옥수수를 수확할 수 있다.

그런데, 민석이는 옥수수의 생산량 조절을 위해서 $K$그루의 옥수수만 수확하려고 한다. 민석이는 현재 수확할 수 있는 옥수수 중에서 가장 가치가 높은 옥수수를 수확하는 과정을 $K$번 반복한다. 민석이가 수확하는 옥수수의 위치를 순서대로 구해보자.

입력

첫째 줄에 정수 $N, M(1 \le N, M \le 1\,000)$이 주어진다.

둘째 줄부터 $N$개의 줄에 걸쳐 $M$개의 정수가 공백으로 구분되어 주어진다. $N$개의 줄 중 $i$번째 줄의 $j$번째 정수는 격자에서 $i$번째 줄의 $j$번째 칸의 옥수수의 가치를 의미하는 정수 $x_{ij}(1 \le x_{ij} \le N \times M)$다.

마지막 줄에 정수 $K(1\le K \le \min(N \times M, 10^5))$가 주어진다.

출력

$K$개의 줄에 민석이가 수확하는 옥수수의 위치 $i, j(1 \le i \le N; 1 \le j \le M)$를 순서대로 출력한다. $i, j$는 격자의 $i$번째 행, $j$번째 열을 의미한다.

예제 입력 1

4 5
1 18 2 3 4
12 17 15 20 5
11 14 19 13 6
10 9 16 8 7
6

예제 출력 1

1 2
2 2
4 3
3 3
2 3
2 4

예제 입력 1

3 3
9 8 1
4 5 2
6 3 7
4

예제 출력 1

1 1
1 2
3 3
3 1