옥수수밭

면접 대비

시간 제한1초메모리 제한1024 MB

요약

격자의 값이 주어질 때, 바깥 테두리에서 시작해 이미 수확한 칸과 인접한 칸 중 가장 큰 값을 K번 골라 그 위치를 순서대로 출력합니다.

난이도: 보통10점 중 4점
유형: 힙, 그리디, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

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

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

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

입력

첫째 줄에 정수 $N$ , $M$ ( $1 \le N, M \le 1\,000$ )이 공백으로 구분되어 주어진다.

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

마지막 줄에 정수 $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$ 는 열을 뜻한다.

예제2

예제 1

입력

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

예상 출력

예제 2

입력

예상 출력