30024번 - 옥수수밭

문제

옥수수밭 주인 민석이는 한 해 동안 열심히 기른 옥수수를 수확하려고 한다. 옥수수밭은 $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$번째 칸의 옥수수의 가치를 의미하는 정수 $a_{ij}(1 \le a_{ij} \le N \times M)$다.

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

출력

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

제한

힌트