The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 4:

- Kotlin 1.4.0

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Dune II: Battle For Arrakis

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou're at the last mission in one very old and very popular strategy game Dune II: Battle For Arrakis. The map of the mission can be represented as a rectangular matrix of size $$$n \times m$$$. Initially, there are $$$a_{i, j}$$$ units of your army in the cell $$$(i, j)$$$.

You want to prepare for the final battle, so you want to move all your army into exactly one cell of the map (i.e. $$$nm-1$$$ cells should contain $$$0$$$ units of the army and the remaining cell should contain the entire army).

To do this, you can do some (possibly, zero) number of moves. During one move, you can select exactly one unit from some cell and move it to one of the adjacent by side cells. I.e. from the cell $$$(i, j)$$$ you can move the unit to cells:

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

Of course, you want to move all your army into exactly one cell as fast as possible. So, you want to know the minimum number of moves you need to do that.

And, of course, life goes on, so the situation on the map changes. There are $$$q$$$ updates, the $$$i$$$-th update is denoted by three integers $$$x, y, z$$$. This update affects the army in the cell $$$(x, y)$$$: after this update, the number of units in the cell $$$(x, y)$$$ becomes $$$z$$$ (i.e. you replace $$$a_{x, y}$$$ with $$$z$$$).

Also, you want to determine, for each $$$i$$$, the minimum number of moves needed to move your entire army into exactly one cell with the first $$$i$$$ updates applied to the initial map. In other words, the map after the $$$i$$$-th update equals the initial map with the first $$$i$$$ updates applied to it.

Input

The first line of the input contains three integers $$$n, m$$$ and $$$q$$$ ($$$1 \le n, m \le 1000; 1 \le q \le 5000$$$) — the size of the matrix and the number of updates correspondingly.

The next $$$n$$$ lines contain $$$m$$$ integers each, where the $$$j$$$-th integer in the $$$i$$$-th line is $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 10^9$$$) — the number of units in the cell $$$(i, j)$$$.

The next $$$q$$$ lines contain three integers each, where the $$$i$$$-th line contains three integers $$$x_i, y_i$$$ and $$$z_i$$$ ($$$1 \le x_i \le n; 1 \le y_i \le m; 1 \le z_i \le 10^9$$$) — the cell in which the number of units updates and the new number of units in this cell correspondingly.

Output

Print $$$q+1$$$ integers $$$r_0, r_1, r_2, \dots, r_n$$$, where $$$r_0$$$ is the minimum number of moves you need to move all your army into exactly one cell, and $$$r_i$$$ for all $$$i$$$ from $$$1$$$ to $$$q$$$ is the minimum number of moves you need to move all your army into exactly one cell after the first $$$i$$$ updates.

Examples

Input

3 3 1 1 2 3 2 1 2 1 1 2 2 3 100

Output

21 22

Input

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

Output

123 135 129 145

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/24/2020 14:50:12 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|