汇点

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定一个 $n$ 行 $m$ 列的网格，每个格子 $(i,j)$ 有一个正整数值 $a_{i,j}$。共享一条边的两个格子相邻。

你可以在任意格子上打洞。一个格子 $(x,y)$ 满足下列条件之一时称为汇点：

• 该格子本身有洞；
• 它相邻于一个已经是汇点的格子 $(i,j)$，并且 $a_{x,y}\ge a_{i,j}$。

网格的美丽值定义为：为了让所有格子都成为汇点，最少需要打多少个洞。

你还需要处理 $q$ 次修改。每次给出 $r,c,x$，把格子 $(r,c)$ 的当前值减少 $x$。每次修改后，假设网格中尚未打任何洞，求当前网格的美丽值。

修改具有累积效果。保证每次修改后所有格子的值仍为正整数。

输入格式

第一行包含整数 $t$，表示测试组数。

每组数据：

• 第一行包含两个整数 $n,m$；
• 接下来 $n$ 行，每行 $m$ 个整数，表示初始网格；
• 接下来一行包含整数 $q$；
• 接下来 $q$ 行，每行包含三个整数 $r,c,x$，表示一次减小操作。

输出格式

对于每组数据输出 $q+1$ 行。

第一行输出初始网格的美丽值；随后依次输出每次修改后的美丽值。

样例输入 1

3
1 4
1 2 3 5
2
1 4 1
1 3 2
3 3
5 1 6
2 9 3
7 4 8
3
2 2 1
2 2 7
3 3 7
3 4
10 10 10 10
10 10 10 10
10 10 11 10
5
3 3 5
2 2 5
2 4 5
2 3 5
1 1 9

样例输出 1

1
1
2
4
4
1
2
1
1
2
3
1
2

数据范围

对于所有数据：

• $1\le t\le10^4$；
• $1\le n,m$，$1\le nm\le2\times10^5$；
• $1\le a_{i,j}\le10^9$；
• $0\le q\le2\times10^5$；
• $1\le r\le n$，$1\le c\le m$，$1\le x<10^9$；
• 所有测试组的 $nm$ 之和不超过 $2\times10^5$；
• 所有测试组的 $q$ 之和不超过 $2\times10^5$；
• 每次修改后所有格子值仍大于 $0$。