P14976 [USACO26JAN1] Photoshoot B

农夫 John 正在一个神奇的牧场里观察他的奶牛，并希望拍摄他的奶牛的子集。 牧场可以看作一个 $N \times N$ 的网格（$1 \leq N \leq 500$），每个位置站着一头静止的奶牛。农夫 John 的相机能够拍摄牧场中任意一个 $K \times K$ 的正方形区域（$1 \leq K \leq \min(N, 25)$）。 在任何时刻，每头奶牛都有一个介于 $0$ 和 $10^6$ 之间的美丽值。一张照片的吸引力指数是照片中所有奶牛美丽值的总和。 每头奶牛的美丽值初始为 $0$，因此一开始任何照片的吸引力指数都是 $0$。 在 $Q$ 个时刻（$1 \leq Q \leq 3 \cdot 10^{4}$），由于吃了农夫 John 牧场中种植的神奇牧草，一头奶牛的美丽值会增加一个正整数。 农夫 John 想知道在每次更新后，他能拍摄到的照片的最大吸引力指数是多少。

第一行包含整数 $N$ 和 $K$。 第二行包含一个整数 $Q$。 接下来的 $Q$ 行，每行包含三个整数：$r$、$c$ 和 $v$，分别表示行、列和新的美丽值（$1 \leq r, c \leq N, 1 \leq v \leq 10^6$）。保证该位置的新美丽值大于该位置之前的美丽值。

输出 $Q$ 行，对应每次更新后照片的最大吸引力指数。

第一次更新后，具有最大吸引力指数的照片是左上角为 $(2, 2)$、右下角为 $(3, 3)$ 的照片，其吸引力指数为 $11 + 0 + 0 + 0 = 11$。 第二次更新不影响最大吸引力指数。 第三次更新后，具有最大吸引力指数的照片变为左上角为 $(2, 1)$、右下角为 $(3, 2)$ 的照片，其吸引力指数为 $0 + 11 + 100 + 0 = 111$。 --- 只有一头奶牛具有正的美丽值，因此最大吸引力指数总是会包含这头奶牛。 --- - 输入 $3$-$6$：$N \leq 50, Q \leq 100$ - 输入 $7$-$10$：$N \leq 50$ - 输入 $11$-$18$：无额外约束。 翻译由 DeepSeek V3 完成