题目描述

嘉音在和伊芙琳拍照。

拍照的区域可以看作一个 $N \times N$ 的网格，嘉音要拍一张 $K \times K$ 的正方形照片，网格里每个位置都有一个闪亮度，拍出的照片的闪亮度是这 $K \times K$ 个位置的闪亮度之和。

每个位置初始闪亮度为 $0$，因此所有照片的闪亮度都是 $0$。

在 $Q$ 个时刻，由于嘉音施加了闪亮的魔法，使得某一个位置的闪亮度永久变成一个比原来更大的正整数。

嘉音想知道，每次施展完魔法之后，她能拍出的照片闪亮度最大是多少。

格式要求

输入格式

第一行包含两个整数 $N$ 和 $K$。 第二行包含一个整数 $Q$。 接下来 $Q$ 行，每行三个整数 $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, 2)$ 右下角 $(3, 3)$ 的照片，闪亮度为 $11$。

第二次更新后，取左上角 $(2, 2)$ 右下角 $(3, 3)$ 的照片，闪亮度为 $11$。

第三次更新后，取左上角 $(2, 1)$ 右下角 $(3, 2)$ 的照片，闪亮度为 $111$。

共 $16$ 个测试点。

测试点 $1 - 4$ 满足 $N \leq 50, Q \leq 100$。

测试点 $5 - 8$ 满足 $N \leq 50$。

测试点 $9 - 16$ 无额外限制。

对于 $100\%$ 的数据，$1 \leq N \leq 500$，$1 \leq K \leq min(N, 25)$，$1 \leq Q \leq 3 \times 10^4$，$1 \leq v \leq 10^6$。