CF1346F.Dune II: Battle For Arrakis

在一款非常古老、非常流行的策略游戏《Dune II: Battle For Arrakis》中，你到了了最后一项任务。大小为n乘以mn×m的矩形矩阵。最初，有一个a[i,j]。你们部队在单元格里的单位（i，j）（i，j）。

你想为最后的战斗做准备，所以你想把你所有的军队移动到地图的一个单元中（即nm-1 nm−1单元格应包含0个陆军单位，其余单元格应包含整个陆军单位）。

要做到这一点，您可以执行一些（可能是零）步数。在一次移动过程中，您可以从某个单元中选择一个单元，然后将其移动到相邻的相邻单元之一。即从单元（I，j）（I，j）可以将单元移动到单元：

（i-1，j）（i）−1，j）；

（i，j-1）（i，j−1) ;

（i+1，j）（i+1，j）；

（i，j+1）（i，j+1）。

当然，你要尽可能快地把你所有的军队转移到一个单元格里。所以，你想知道你需要做的最小移动次数。

并且，当然，生活还在继续，所以地图上的情况发生了变化。有q更新，第i次更新由三个整数x，y，zx，y，z表示。此更新影响单元（x，y）（x，y）中的陆军：此更新后，单元（x，y）（x，y）中的单位数变为z（即用z替换a[x,y]）。

此外，您还需要确定，对于每个i，将整个军队移动到一个单元所需的最小移动次数，并将第一次i更新应用于初始地图。换句话说，第i次更新后的映射等于应用了第一次i次更新的初始映射。

输入的第一行包含三个整数n、mn、m和q（1\le n、m\le 1000；1\le q\le 5000 1≤n、 m≤1000;1≤q≤5000）-矩阵的大小和相应的更新次数。

接下来的n n行包含m m个整数，其中第i行中的第j个整数是a[i，j]（1≤a[i,j]≤10^9))-单元中的单元数（i，j）（i，j）。

接下来的q行各包含三个整数，其中第i行包含三个整数x_i，y_i还有z_i（1≤x_i≤n;1≤y_i≤m;1≤z_i≤10^9)-单元数更新的单元以及该单元中相应的新单元数。

打印q+1整数r_0，r_1，r_2，…r_n，其中r_0是将所有军队移动到一个单元格中所需的最小移动次数，r_i表示从1到q q的所有i i i是在第一次i更新后将所有军队移动到一个单元格中所需的最小移动次数。