样例下载

题目描述

二维平面地图上有 $n^2$ 个目标，均匀分布在以点 (1,1) 和 (n,n) 作为对角的正方形内每个整点（即点的 x 和 y 坐标均为整数）处，每个目标有一个重要度，初始时所有目标的重要度均为 0。接下来有 T 个时刻，每过一个时刻，会有一个目标的重要度增大。

一种新型的激光炸弹，可以摧毁一个边长为 $m$ 的正方形内的所有目标。激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 $m$ 的边必须与 $x$ 轴或 $y$ 轴平行。若某目标位于爆破正方形的边上，则该目标不会被摧毁。

现在你的任务是计算：每过一个时刻，当有一个目标的重要度增大后，如果在此时投放一颗激光炸弹，所能摧毁的所有目标的重要度之和最大是多少？

输入格式

第一行：两个整数 $n$ 和 $m$。

第二行：一个整数 $T$。

接下来 $T$ 行，每行三个整数：$x_i$、$y_i$ 和 $z_i$，表示位于坐标 $(x_i, y_i)$ 处的目标的重要度增大为 $z_i$。数据保证该坐标处最新的重要度 $z_i$ 的值一定比之前大。

输出格式

共 $T$ 行，每行一个整数，表示一个目标的重要度增大后对应的答案。

样例输入

5 2
3
1 2 3
4 5 6
2 3 4

样例输出

3
6
7

数据范围

100% 的数据满足 $1 ≤ n ≤ 500$, $1 ≤ m ≤ \min(n, 50)$, $1 ≤ T ≤ 30000$, $1 ≤ x_i, y_i ≤ n, 1 ≤ z_i ≤ 10^6$）。其中：

• 10% 的数据：$n ≤ 50, T ≤ 100$
• 20% 的数据：$n ≤ 50$