라듐 채굴

메리디아니 평원에서 라듐을 채굴하기 전 지질 탐사를 위해, 화성 궤도에 표면의 방사능 수치를 측정하는 특수 위성이 발사되었다.

평원을 $n \times m$개의 단위 정사각형으로 이루어진 직사각형으로 나타내고, $i$번째 행의 $j$번째 정사각형을 $(i, j)$로 표기한다.

평원을 스캔한 결과 각 단위 정사각형의 방사능 수치가 정해졌다. 정사각형 $(i, j)$의 방사능 수치는 양의 정수 $a_{ij}$로 주어진다. 측정 정밀도가 매우 높아 모든 수 $a_{ij}$는 서로 다르다. 단위 정사각형 $(i, j)$는 값 $a_{ij}$가 $i$번째 행에서 최대이고 $j$번째 열에서도 최대일 때 라듐 채굴에 적합하다고 본다.

관측 과정에서 방사능 수치를 $q$번에 걸쳐 순차적으로 갱신했다. 즉, $k$번째 갱신은 $a_{r_k c_k}$의 값을 어떤 엄격히 더 큰 값으로 바꾸었다. 각 갱신 후에도 모든 값 $a_{ij}$는 서로 달랐다.

초기값 $a_{ij}$와 갱신 목록이 주어졌을 때, 각 갱신 후 라듐 채굴에 적합한 단위 정사각형의 개수를 구하는 프로그램을 작성하라.

입력의 첫째 줄에는 세 개의 양의 정수 $n$, $m$, $q$가 주어진다 ($1 \le n\times m \le 200\,000$, $1 \le q \le 200\,000$). 상한은 행과 열의 개수에 각각 주어지는 것이 아니라 평원의 넓이에 주어진다는 점에 주의하라.

다음 $n$개 줄에는 각각 $m$개의 양의 정수가 주어지고, 이 줄들 중 $i$번째 줄의 $j$번째 수가 $a_{ij}$의 초기값을 나타낸다 ($1 \le a_{ij} \le 10^7$, 모든 $a_{ij}$는 서로 다르다).

다음 $q$개 줄은 데이터 갱신을 나타내고, 그중 $k$번째 줄에는 세 개의 정수 $r_k$, $c_k$, $x_k$가 주어지며, 단위 정사각형 $(r_k, c_k)$의 방사능 수치 정보를 바꾸는 것을 나타내고 새 값은 $x_k$이다 ($1 \le r_k \le n$, $1 \le c_k \le m$, $1 \le x_k \le 10^7$). $x_k$는 이 정사각형의 이전 방사능 수치보다 엄격히 크고, 각 변경 후 모든 방사능 수치가 서로 다르다는 것이 보장된다.

출력에는 $q$개 줄이 있어야 하고, 그중 $k$번째 줄에는 $k$번째 정보 갱신 후 라듐 채굴에 적합한 단위 정사각형의 개수를 하나의 수로 출력한다.