20446번 - Добыча радия 서브태스크다국어

문제

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

Представим плато как прямоугольник, состоящий из $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$-го обновления информации.

제한

서브태스크

힌트