F. Dune II: Battle For Arrakis
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы дошли до последней миссии в очень старой и очень популярной стратегии Dune II: Battle For Arrakis. Карта этой миссии может быть представлена в виде прямоугольной матрицы размера $$$n \times m$$$. Изначально, в клетке $$$(i, j)$$$ стоит $$$a_{i, j}$$$ отрядов вашей армии.

Вы готовитесь к последней битве, поэтому вы хотите собрать всю вашу армию в ровно одну клетку на карте (то есть $$$nm-1$$$ клетка должна содержать $$$0$$$ отрядов, а оставшаяся клетка должна содержать всю армию).

Чтобы достичь этого, вы можете совершить несколько (возможно, ноль) ходов. За один ход можно выбрать ровно один отряд из некоторой клетки и отправить его в соседнюю по стороне клетку. То есть из клетки $$$(i, j)$$$ можно отправить отряд в клетки:

  • $$$(i - 1, j)$$$;
  • $$$(i, j - 1)$$$;
  • $$$(i + 1, j)$$$;
  • $$$(i, j + 1)$$$.

Разумеется, вы хотите собрать армию в ровно одной клетке как можно быстрее. Поэтому вы хотите узнать минимальное необходимое для этого число ходов.

Также, жизнь не стоит на месте, а ситуация на карте меняется. Всего есть $$$q$$$ изменений, $$$i$$$-е изменение задается тремя целыми числами $$$x, y, z$$$. Это изменение затрагивает армию в клетке $$$(x, y)$$$: после этого изменения количество отрядов в клетке $$$(x, y)$$$ становится $$$z$$$ (то есть $$$a_{x, y}$$$ заменяется на $$$z$$$).

Также вы хотите знать для каждого $$$i$$$ минимальное количество ходов, необходимое для сбора всей армии в ровно одной клетке после применения первых $$$i$$$ изменений к изначальной карте. Другими словами, карта после $$$i$$$-го изменения равна изначальной карте с первыми $$$i$$$ изменениями, примененными к ней.

Входные данные

В первой строке записаны три целых числа $$$n, m$$$ и $$$q$$$ ($$$1 \le n, m \le 1000; 1 \le q \le 5000$$$) — размеры матрицы и количество изменений, соответственно.

Каждая из следующих $$$n$$$ строк содержит по $$$m$$$ целых чисел, где $$$j$$$-е число $$$i$$$-й строки — это $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 10^9$$$) — количество отрядов в клетке $$$(i, j)$$$.

В каждой из следующих $$$q$$$ строк записаны три целых числа, в $$$i$$$-й строке записаны три целых числа $$$x_i, y_i$$$ и $$$z_i$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m; 1 \le z_i \le 10^9$$$) — клетка, в которой изменяется количество отрядов, и новое количество отрядов, соответственно.

Выходные данные

Выведите $$$q+1$$$ целое число $$$r_0, r_1, r_2, \dots, r_n$$$, где $$$r_0$$$ — это минимальное количество ходов, необходимые для сбора всей армии в ровно одной клетке, а $$$r_i$$$ для каждого $$$i$$$ от $$$1$$$ до $$$q$$$ — минимальное количество ходов, необходимые для сбора всей армии в ровно одной клетке, после $$$i$$$ изменений.

Примеры
Входные данные
3 3 1
1 2 3
2 1 2
1 1 2
2 3 100
Выходные данные
21 22
Входные данные
4 4 3
2 5 6 3
4 8 10 5
2 6 7 1
8 4 2 1
1 1 8
2 3 4
4 4 5
Выходные данные
123 135 129 145