您正在执行一款非常古老且非常流行的策略游戏《沙丘 II:厄拉基斯之战》中的最后一个任务。任务地图可以表示为大小为 $$$n \times m$$$ 的矩形矩阵。最初,单元格 $$$(i, j)$$$ 中有你军队的 $$$a_{i, j}$$$ 单位。
你想为最后的战斗做准备,所以你想将你的所有军队移动到地图的一个单元格中(即 $$$nm-1$$$ 单元格应包含军队的 $$$0$$$ 单位,其余单元格应包含整个军队)。
为此,您可以进行一些(可能是零)移动。在一次移动过程中,您可以从某个单元格中精确选择一个单位并将其移动到相邻的旁边单元格之一。 IE。从单元格 $$$(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$$$ 个整数,其中第 $$$i$$$ 行中的第 $$$j$$$ 整数是 $$$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$$$ 是从 $$$1$$$ 到 $$$q$$$ 的所有 $$$i$$$ 的最小移动数移动 您需要在第一个 $$$i$$$ 更新后将所有军队移动到一个单元格中。
示例
输入 #1
3 3 1 1 2 3 2 1 2 1 1 2 2 3 100
输出 #1
21 22
输入 #2
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
输出 #2
123 135 129 145