农夫约翰正在一片魔法草地上观察他的奶牛，想要拍摄部分奶牛的照片。

这片草地可看作一个 N×N 的网格（1 ≤ N ≤ 500），每个位置上都有一头静止的奶牛。农夫约翰的相机可以拍摄草地中任意一个 K×K 的正方形区域（1 ≤ K ≤ min (N, 25)）。

任何时刻，每头奶牛的魅力值都在 0 到 10⁶ 之间。一张照片的吸引力指数等于照片中包含的所有奶牛的魅力值之和。

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

接下来会发生 Q 次更新（1 ≤ Q ≤ 3×10⁴）：每一次，某一头奶牛会因为食用了农夫约翰草地上种植的魔法草，其魅力值增加一个正整数（注：题目中 “new beauty value” 指更新后的总魅力值，且保证该值大于更新前的魅力值）。

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

输入格式（输入从终端 / 标准输入读取）

第一行包含两个整数 N 和 K。

第二行包含一个整数 Q。

接下来 Q 行，每行包含三个整数 r、c 和 v，分别表示奶牛所在的行、列以及更新后的魅力值（1 ≤ r, c ≤ N，1 ≤ v ≤ 10⁶）。保证更新后的魅力值大于该位置之前的魅力值。

输出格式（输出到终端 / 标准输出）

输出 Q 行，分别对应每一次更新后能拍摄到的照片的最大吸引力指数。

示例输入 1

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

示例输出 1

11
11
111

第一次更新后，吸引力指数最大的照片是左上角为 (2, 2)、右下角为 (3, 3) 的正方形区域，其吸引力指数为 11 + 0 + 0 + 0 = 11。

第二次更新不会影响最大吸引力指数。

第三次更新后，吸引力指数最大的照片变为左上角为 (2, 1)、右下角为 (3, 2) 的正方形区域，其吸引力指数为 0 + 11 + 100 + 0 = 111。

示例输入 2

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

示例输出 2

3
5
7

只有一头奶牛的魅力值为正数，因此最大吸引力指数始终包含这头奶牛（注：K=1 时，照片为 1×1 正方形，即单头奶牛，因此最大吸引力指数就是该奶牛的魅力值）。

评分标准

• 输入 3-6：N ≤ 50，Q ≤ 100；
• 输入 7-10：N ≤ 50；
• 输入 11-18：无额外限制。