22956번 - 소나기

문제

신촌에는 $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번의 그림이다.