题目描述

有一块 \(N \times N\) 的网格草地，满足 \(1 \le N \le 500\)。每个格子里都站着一头固定不动的奶牛。

Farmer John 的相机可以拍摄草地中的任意一个 \(K \times K\) 的正方形区域，其中 \(1 \le K \le \min(N,25)\)。

每头奶牛都有一个美丽值，范围在 \(0\) 到 \(10^6\) 之间。一张照片的“吸引力”定义为照片中所有奶牛美丽值之和。

初始时所有奶牛的美丽值都是 \(0\)，因此一开始任意照片的吸引力都是 \(0\)。

接下来会发生 \(Q\) 次更新，满足 \(1 \le Q \le 3 \cdot 10^4\)。每次更新会让某个格子中的奶牛因为吃到神奇牧草而把美丽值提高到一个新的正整数。

请你在每次更新后，输出当前所有 \(K \times K\) 照片中，吸引力的最大值。

输入格式

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

第二行包含一个整数 \(Q\)。

接下来 \(Q\) 行，每行包含三个整数 \(r, c, v\)，表示第 \(r\) 行第 \(c\) 列的奶牛美丽值被更新为 \(v\)，满足：

• \(1 \le r,c \le N\)
• \(1 \le v \le 10^6\)

保证新的美丽值严格大于该位置之前的美丽值。

输出格式

输出 \(Q\) 行，第 \(i\) 行表示第 \(i\) 次更新后的答案。

样例 1

输入

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

输出

11
11
111

说明

第一次更新后，吸引力最大的照片可以是左上角为 \((2,2)\)、右下角为 \((3,3)\) 的那个 \(2 \times 2\) 方块，其吸引力为 \(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

输出

3
5
7

说明

由于 \(K=1\)，每张照片只包含一头奶牛，因此答案始终等于当前全场最大的美丽值。

数据范围

• 输入 3-6：\(N \le 50, Q \le 100\)
• 输入 7-10：\(N \le 50\)
• 输入 11-18：无额外限制

命题信息

原题命题：Brian Law 和 Cici Liu