Для геологической разведки перед добычей радия на плато Меридиана на орбиту Марса выведен специальный спутник, позволяющий измерять уровень радиоактивности на поверхности.
Представим плато как прямоугольник, состоящий из $$$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$$$-го обновления информации.
$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Подзадача} & \text{Баллы} & \text{Ограничения} & \text{Необх. подзадачи} \\ \hline 1 & 25 & 1 \le n \cdot m \le 100, 1 \le q \le 100 & 0 \\ \hline 2 & 25 & 1 \le n \cdot m \le 5000, 1 \le q \le 5000 & 0, 1 \\ \hline 3 & 25 & 1 \le n, m \le 400, 1 \le q \le 200\,000 & 0, 1 \\ \hline 4 & 25 & 1 \le n \cdot m \le 200\,000, 1 \le q \le 200\,000 & 0, 1, 2, 3 \\ \hline \end{array}$$$$$$
Вам будут начислены баллы за группу, только если пройдены все тесты этой группы и во всех группах, от которых она зависит. Группа $$$0$$$ соответствует примерам из условия.
2 3 3 1 4 3 6 5 2 2 2 9 1 3 5 2 2 10
1 2 2
