Farmer John 正在一片神奇的牧场上看着他的奶牛，并想给他的奶牛子集拍一些照片。

牧场可以看作一个 $N \times N$ 的网格 $(1 \leq N \leq 500)$，每个位置上都有一头静止不动的奶牛。Farmer 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})$，某头奶牛的美丽值会因为吃了 Farmer John 牧场上种植的神奇牧草而增加一个正整数。

Farmer John 想要知道在每次更新后，他能拍到的照片的最大吸引力指数是多少。

输入格式

第一行包含整数 $N$ 和 $K$。

下一行包含一个整数 $Q$。

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

输出格式

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

样例

输入样例 1

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

输出样例 1

11
11
111

说明 1

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

说明 2

只有一头奶牛具有正的美丽值，因此最大吸引力指数总是会包含这头奶牛。

子任务

• 测试点 3-6：$N \leq 50, Q \leq 100$
• 测试点 7-10：$N \leq 50$
• 测试点 11-18：无额外限制。