시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB222100.000%

문제

Для геологической разведки перед добычей радия на плато Меридиана на орбиту Марса выведен специальный спутник, позволяющий измерять уровень радиоактивности на поверхности. 

Представим плато как прямоугольник, состоящий из $n \times m$ единичных квадратов, обозначим $j$-й квадрат в $i$-м ряду как $(i, j)$. 

В результате сканирования плато для каждого единичного квадрата был определён уровень радиоактивности. Уровень радиоактивности квадрата $(i, j)$ задаётся целым положительным числом $a_{ij}$. Точность измерений настолько велика, что все числа $a_{ij}$ различны. Единичный квадрат $(i, j)$ считается подходящим для добычи радия, если значение $a_{ij}$ является максимальным в $i$-й строке, а также максимальным в $j$-м столбце. 

В процессе наблюдений было проведено $q$ последовательных уточнений уровня радиоактивности. А именно, $k$-е уточнение изменяло значение $a_{r_kc_k}$ на некоторое строго большее значение. При этом после каждого уточнения все значения $a_{ij}$ оставались различными.

Требуется написать программу, которая по заданным исходным значениям $a_{ij}$ и списку уточнений после каждого уточнения информации определяет количество подходящих для добычи радия единичных квадратов.

입력

Первая строка входных данных содержит три положительных целых числа: $n$, $m$ и $q$ ($1 \le n\times m \le 200\,000$, $1 \le q \le 200\,000$). Обратите внимание, что ограничение сверху дано на площадь плато, а не на количество столбцов и строк по отдельности.

Следующие $n$ строк содержат по $m$ положительных целых чисел, $j$-е число в $i$-й из этих строк задаёт начальное значение $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$-го обновления информации.

서브태스크

번호배점제한
125

$1 \le n\times m \le 100$, $1 \le q \le 100$

225

$1 \le n\times m \le 5000$, $1 \le q \le 5000$

325

$1 \le n \le 400$, $1 \le m \le 400$, $1 \le q \le 200\,000$

425

$1 \le n\times m \le 200\,000$, $1 \le q \le 200\,000$

예제 입력 1

2 3 3
1 4 3
6 5 2
2 2 9
1 3 5
2 2 10

예제 출력 1

1
2
2

채점 및 기타 정보

  • 예제는 채점하지 않는다.