描述

农夫约翰正在观察他位于一个神奇田地中的奶牛，并希望拍摄一些奶牛子集的照片。

这片田地可以看作一个 $N \times N$ 的网格（$1 \le N \le 500$），每个格子上都有一头静止的奶牛。他的相机能够拍摄田地中任意一个 $K \times K$ 的正方形区域（$1 \le K \le \min(N, 25)$）。

每头奶牛在任意时刻都有一个美丽值，范围在 0 到 $10^6$ 之间。一张照片的吸引力指数定义为照片中所有奶牛美丽值的总和。

初始时，所有奶牛的美丽值均为 0，因此任何照片的吸引力指数初始也为 0。

在接下来的 $Q$ 个时间点（$1 \le Q \le 3 \cdot 10^4$），某头奶牛的美丽值会因为吃了魔法草而增加一个正整数。

农夫约翰希望知道，在每一次更新之后，他能拍摄到的照片的最大吸引力指数是多少。

输入输出格式

输入

第一行包含两个整数 $N$ 和 $K$，表示网格大小和拍照区域的边长。 第二行包含一个整数 $Q$，表示更新的次数。 接下来 $Q$ 行，每行包含三个整数 $r, c, v$，表示第 $r$ 行第 $c$ 列的奶牛美丽值被更新为 $v$（保证新值大于旧值）。

输出

输出 $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.0 秒
• 空间限制：256 MB
• $1 \le N \le 500$
• $1 \le K \le \min(N, 25)$
• $1 \le Q \le 3 \cdot 10^4$
• $1 \le r, c \le N$
• $1 \le v \le 10^6$，且每次更新的值严格大于该位置之前的值