CF2158E.Sink

You are given a grid containing $n$ rows and $m$ columns. Every cell $(i, j)$, located in the $i$-th row and $j$-th column, has a positive integer value associated with it $a_{i, j}$. Two cells are adjacent if and only if they share a common side in the grid.

You are allowed to construct holes at cells of your choice. A cell $(x, y)$ is a sink if and only if it has a hole, or is adjacent to a sink $(i, j)$ with $a_{x, y} \ge a_{i, j}$.

The beauty of a grid is defined as the minimum number of holes you need to construct so that every cell becomes a sink.

You have to determine the beauty of this grid.

You are also given $q$ queries.

In a query, you are given three positive integers $r$, $c$, and $x$. The current value of cell $(r, c)$ is decreased by $x$. After each query, determine the beauty of the grid considering no holes have been constructed yet.

Note that queries are cumulative, so the effects of each query carry on to future queries.

It is guaranteed that after every query the value of each cell will remain positive.

你被给定一个包含 $n$ 行和 $m$ 列的网格。每个位于第 $i$ 行、第 $j$ 列的单元格 $(i, j)$ 都关联着一个正整数 $a_{i, j}$。当且仅当两个单元格在网格中共享一条公共边时，它们才被认为是相邻的。

你可以选择在任意单元格上“开洞”。单元格 $(x, y)$ 被称为汇点（sink），当且仅当它本身被开了洞，或者它与某个汇点 $(i, j)$ 相邻，且满足 $a_{x, y} \ge a_{i, j}$。

该网格的美观度（beauty） 定义为：使得所有单元格均成为汇点所需的最少开洞数量。

你需要计算该网格的美观度。

此外，你还会收到 $q$ 个查询。

每次查询中，你将获得三个正整数 $r$、$c$ 和 $x$，表示将当前单元格 $(r, c)$ 的值减少 $x$。在每次查询之后，请计算当前网格的美观度（注意：此时尚未开任何洞）。

注意：这些查询是累积生效的，即每次查询对网格状态的修改会持续影响后续所有查询。

保证每次查询后，每个单元格的值仍保持为正整数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le n \cdot m \le 2 \cdot 10^5$) — the number of rows and columns, respectively.

The following $n$ lines contain $m$ integers each; the $j$-th element in the $i$-th line $a_{i, j}$ is the number written in the $j$-th cell of the $i$-th row ($1 \le a_{i,j} \le 10^9$).

The next line contains a single integer $q$ ($0 \le q \le 2\cdot 10^5$) — the number of queries.

The following $q$ lines contain $3$ integers each — $r, c,$ and $x$ ($1\le r \le n, 1\le c \le m, 1\le x \lt 10^9$).

It is guaranteed that the sum of $n \cdot m$ and the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

It is guaranteed that after every query the value of each cell will remain positive.

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$，且 $1 \le n \cdot m \le 2 \cdot 10^5$），分别表示行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个整数；其中第 $i$ 行的第 $j$ 个元素 $a_{i, j}$ 表示第 $i$ 行第 $j$ 列单元格中所写的数字（$1 \le a_{i,j} \le 10^9$）。

下一行包含一个整数 $q$（$0 \le q \le 2\cdot 10^5$），表示查询次数。

接下来的 $q$ 行，每行包含三个整数 $r$、$c$ 和 $x$（$1\le r \le n$，$1\le c \le m$，$1\le x \lt 10^9$）。

保证所有测试用例中 $n \cdot m$ 的总和以及 $q$ 的总和均不超过 $2 \cdot 10^5$。

保证每次查询后，每个单元格的值均保持为正数。

For each test case, print $q+1$ lines.

On the first line print the beauty of the initial grid.

Also, after each query, print the beauty of the current grid.

对于每个测试用例，输出 $q+1$ 行。

第一行输出初始网格的美观度。

此外，在每次查询之后，输出当前网格的美观度。

For the first test case:

• Initially, we can create a hole at cell ($1,1$).
• After the first query, we can create a hole at cell ($1,1$).
• After the second query, we can create holes at cells ($1,1$) and ($1,3$).

For the second test case:

• Initially, we can create holes at cells ($1,2$), ($2,1$), ($2,3$), and ($3,2$).
• After the first query, we can create holes at cells ($1,2$), ($2,1$), ($2,3$), and ($3,2$).
• After the second query, we can create a hole at cell ($2,2$).
• After the third query, we can create holes at cells ($2,2$) and ($3,3$).

对于第一个测试用例：

• 最初，我们可以在单元格 ($1,1$) 处创建一个洞。
• 第一次查询后，我们可以在单元格 ($1,1$) 处创建一个洞。
• 第二次查询后，我们可以在单元格 ($1,1$) 和 ($1,3$) 处创建洞。

对于第二个测试用例：

• 最初，我们可以在单元格 ($1,2$)、($2,1$)、($2,3$) 和 ($3,2$) 处创建洞。
• 第一次查询后，我们可以在单元格 ($1,2$)、($2,1$)、($2,3$) 和 ($3,2$) 处创建洞。
• 第二次查询后，我们可以在单元格 ($2,2$) 处创建一个洞。
• 第三次查询后，我们可以在单元格 ($2,2$) 和 ($3,3$) 处创建洞。