P14976 [USACO26JAN1] Photoshoot B

Farmer John is looking at his cows in a magical field and wants to take pictures of subsets of his cows. The field can be seen as a $N \times N$ grid $(1 \leq N \leq 500)$, with a single stationary cow at each location. Farmer John's camera is capable of taking a picture of any $K \times K$ square that is part of the field $(1 \leq K \leq \min(N, 25))$. At all times, each cow has a beauty value between $0$ and $10^6$. The attractiveness index of a picture is the sum of the beauty values of the cows contained in the picture. The beauty value for every cow starts out as $0$, so the attractiveness index of any picture in the beginning is $0$. At $Q$ times $(1 \leq Q \leq 3\cdot 10^{4})$, the beauty of a single cow will increase by a positive integer due to eating the magical grass that is planted on Farmer John's field. Farmer John wants to know the maximum attractiveness index of a picture he can take after each of the $Q$ updates.

The first line contains integers $N$ and $K$. The following line contains an integer $Q$. Each of the following $Q$ lines contains three integers: $r$, $c$, and $v$, which are the row, column, and new beauty value, respectively ($1 \leq r, c \leq N, 1 \leq v \leq 10^6$). It is guaranteed that the new beauty value is greater than the beauty value at that location before.

Output $Q$ lines, corresponding to the maximum attractiveness index of a picture after each update.

After the first update, a picture with the maximum attractiveness index is the picture with upper left corner $(2, 2)$ and lower right corner $(3, 3)$, which has an attractiveness index of $11 + 0 + 0 + 0 = 11$. The second update does not affect the maximum attractiveness index. After the third update, the picture with the maximum attractiveness index changes to the picture with upper left corner $(2, 1)$ and lower right corner $(3, 2)$, which has an attractiveness index of $0 + 11 + 100 + 0 = 111$. --- There is only one cow with a positive beauty value, so the maximum attractiveness index will always include that cow. --- - Inputs 3-6: $N \leq 50, Q \leq 100$ - Inputs 7-10: $N \leq 50$ - Inputs 11-18: No additional constraints.