시간 제한메모리 제한제출정답맞은 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)63312764.286%

문제

신촌에는 $N \times M$ 크기의 신촌평야가 있다. 이 신촌평야에 $Q$일간 소나기가 온다고 한다. 신촌평야의 좌측 상단의 좌표는 ($1$, $1$)이며, 우측 하단의 좌표는 ($N$, $M$)이다.

소나기는 ($a$, $b$) 칸에 내리며, 내린 후에는 땅의 높이가 $c$만큼 감소하며 해당 칸에 물이 남는다. 땅의 높이는 음수가 될 수 있다.

만약 인접한 칸에 물이 있다면 각 칸의 물이 연결된다. 각 칸이 한 개의 변을 공유하고 있으면 두 칸이 인접한다고 한다.

신촌평야 관리본부에서는 수질검사를 위해 소나기가 내린 후 그 지점에 수질 검사 로봇을 설치한다. 이 로봇은 연결된 물로 자유롭게 이동하다가 높이가 가장 낮은 칸에서 검사를 마친다. 만약 높이가 가장 낮은 칸이 여러 개 있다면, 비가 내린 지 가장 오래된 칸에서 검사를 마친다. 

총 $Q$일간 소나기가 내릴 곳이 주어질 때, 각 날짜마다 로봇이 검사를 마치는 지점을 출력하는 프로그램을 만들어 보자.

입력

첫 번째 줄에 공백을 기준으로 $N$ ($1 \le N \le 1\,000$),  $M$ ($1 \le M \le 1\,000$), $Q$ ($1 \le Q \le 100\,000$)가 정수로 주어진다.

두 번째 줄부터 $N+1$ 번째 줄까지 신촌평야의 각 칸의 높이 정보 $H$ ($0 \le H_{a, b} \le 1\,000$ ) 가 정수로 주어진다. 

$N+2$ 번째 줄부터 $N+Q+1$ 번째 줄까지 순서대로 비가 올 칸의 좌표인 $a$ ($1 \le a \le N$), $b$ ($1 \le b \le M$), 땅의 높이가 감소되는 정도인 $c$ ($1 \le c \le 100$) 가 정수로 주어진다.

출력

각 날짜마다 로봇이 검사를 마치는 지점의 좌표를 한 줄씩 차례대로 출력한다.

예제 입력 1

2 3 5
9 9 9
9 9 9
1 1 1
1 2 2
2 2 2
1 1 5
1 2 1

예제 출력 1

1 1
1 2
1 2
1 1
1 1

예제 입력 2

4 5 14
0 9 9 9 9
9 9 0 0 0
0 9 0 0 0
0 9 9 9 0
1 4 1
1 3 1
1 2 1
1 5 2
4 3 1
4 2 1
3 2 1
4 4 2
2 1 2
2 2 1
2 2 1
1 2 1
1 2 1
1 5 1

예제 출력 2

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

힌트

다음은 예제 1번의 그림이다.