E. Водосток
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана сетка, содержащая $$$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$$$ целых чисел; $$$j$$$-й элемент в $$$i$$$-й строке $$$a_{i, j}$$$ — это число, записанное в $$$j$$$-й ячейке $$$i$$$-й строки ($$$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$$$ строк.

В первой строке выведите красоту начальной сетки.

Также после каждого запроса выведите красоту текущей сетки.

Пример
Входные данные
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
2
4
4
1
2
1
1
2
3
1
2
Примечание

Для первого набора входных данных:

  • Изначально мы можем создать дыру в ячейке ($$$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$$$).