题目描述

农夫 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$ 行，对应每次更新后照片的最大吸引力指数。

4 2
3
2 2 11
3 4 3
3 1 100

11
11
111

3 1
3
2 2 3
2 2 5
2 2 7

3
5
7

提示

第一次更新后，具有最大吸引力指数的照片是左上角为 $(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 完成