给您一个包含 $$$n$$$ 行和 $$$m$$$ 列的网格。位于第 $$$i$$$ 行和第 $$$j$$$ 列的每个单元格 $$$(i, j)$$$ 都有一个与其关联的正整数值 $$$a_{i, j}$$$。当且仅当两个单元在网格中共享公共边时,它们才是相邻的。
您可以构建 孔 在您选择的单元格。单元格 $$$(x, y)$$$ 是 水槽 当且仅当它有一个洞,或者与 $$$(i, j)$$$ 且 $$$a_{x, y} \ge a_{i, j}$$$ 的水槽相邻。 网格的
的 美女 被定义为您需要构建的最小孔数,以便每个单元都成为一个水槽。
你必须确定这个网格的美感。
您还会收到 $$$q$$$ 查询。
在查询中,您将获得三个正整数 $$$r$$$、$$$c$$$ 和 $$$x$$$。单元格 $$$(r, c)$$$ 的当前值减少 $$$x$$$。每次查询后,考虑到尚未构建孔洞,确定网格的美观程度。
请注意,查询是累积的,因此每个查询的影响都会延续到未来的查询。
保证每次查询后每个单元格的值将保持正值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 行分别包含 $$$3$$$ 整数 — $$$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$$$。
保证每次查询后每个单元格的值将保持正值。
输出
对于每个测试用例,打印 $$$q+1$$$ 行。
在第一行打印初始网格的美丽。
另外,每次查询后,打印当前网格的美度。
示例
输入复制
31 41 2 3 521 4 11 3 23 35 1 62 9 37 4 832 2 12 2 73 3 73 410 10 10 1010 10 10 1010 10 11 1053 3 52 2 52 4 52 3 51 1 9
输出复制
1124412112312
注意
对于第一个测试用例:
- 最初,我们可以在单元格 ($$$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$$$) 处创建孔。