Добыча радия

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

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