405879: GYM102147 A Extraction of radium

Before mining radium on Mars is possible, a special satellite was launched to measure the radioactivity level on the surface of the planet.

The plateau (flat piece of land) Meridian can be represented as a rectangle with $$$n \times m$$$ unit squares. We denote the $$$j$$$-th square in the $$$i$$$-th row as $$$(i, j)$$$. Both rows and columns are numbered starting from $$$1$$$.

As a result of scanning the plateau, we know the level of radioactivity for each unit square. For the unit square $$$(i, j)$$$ it is a positive integer $$$a_{ij}$$$. The accuracy of the measurements is so high that all numbers $$$a_{ij}$$$ are different. A unit square is considered suitable for the extraction of radium if its value $$$a_{ij}$$$ is the maximum in the $$$i$$$-th row and the maximum in the $$$j$$$-th column.

The satellite then recorded $$$q$$$ updates in the radioactivity. The $$$k$$$-th update changed the value $$$a_{r_k c_k}$$$ to a stricly greater value. (The radioactivity on Mars tends to increase.) The new value stays in this unit square forever unless a new update changes the same unit square. After each update, all values $$$a_{ij}$$$ are guaranteed to still remain different.

Your task is to write a program that, given the initial values $$$a_{ij}$$$ and the list of updates, after each update determines the number of unit squares that are suitable for the extraction of radium.

The first line of the input contains three positive integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n \cdot m \le 200\,000$$$, $$$1 \le q \le 200\,000$$$). Please note that the first constraint is for the product $$$n \cdot m$$$, not for the number of rows and columns separately.

Each of the following $$$n$$$ lines contains $$$m$$$ positive integers. The $$$j$$$-th integer in the $$$i$$$-th of those lines specifies the initial value $$$a_{ij}$$$ ($$$1 \le a_{ij} \le 10^7$$$, all $$$a_{ij}$$$ are different).

The following $$$q$$$ lines describe the updates. The $$$k$$$-th of them contains three integers $$$r_k$$$, $$$c_k$$$ and $$$x_k$$$, that denote the change in the level of radioactivity in the unit square $$$(r_k, c_k)$$$ to a new value $$$x_k$$$ ($$$1 \le r_k \le n$$$, $$$1 \le c_k \le m$$$, $$$1 \le x_k \le 10^7$$$). It is guaranteed that $$$x_k$$$ is strictly greater than the previous level of radioactivity in this square, and that all the radioactivity levels are different after each update.

The output should consist of $$$q$$$ lines. In the $$$k$$$-th line, print a single integer — the number of unit squares suitable for the extraction of radium after the $$$k$$$-th update.

$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \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}$$$$$$

You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.

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

1
2
2