分数: 100 点
问题陈述
JOI的国家是一个等边三角形,边长 L 其顶点是点 A, B,和 C。 在这里, L 是正整数。 侧面 AB 连接顶点 A 和 B 东西方向,且顶点 A 是JOI所在国家的最西点,而顶点 B 是最东点。 顶点 C 是JOI国的最北点。
JOI的国家分为 L^2 地区,每个都是边长为等边三角形 1。 作为某个区域的顶点的点称为 格点。 对于整数 x, y 满意 0\leq y\leq L 和 0\leq x\leq L-y,即格点 (1+y)-st 从南方和 (1+x)从西起的 -st 表示为 (x,y)。 特别是, A, B,和 C 表示为 分别是 (0,0), (L,0),和 (0,L)。 例如,下图显示了当 L=5.

在 JOI 的国家, 下一个天气预报 N 天数已公布。 当天 i,预计三角形区域有雨 T_i 其顶点是格点 (X_i, Y_i), (X_i + Z_i, Y_i),和 (X_i, Y_i + Z_i)。 据说某地区预计当天会下雨 i 如果整个区域包含在 T_i.
为了防备降雨造成的灾害,有必要确定每个 k=1,2,\ldots,K,预计至少有降雨的地区数量 k 天。
鉴于 JOI 国家的大小、天气预报和 K,编写一个程序,对于每个 k=1,2,\ldots,K,计算预计至少在 k 天。
输入
输入由标准输入按以下格式给出:
L N K X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_N Y_N Z_N
输出
打印 K 行连接到标准输出。 的 k- 第行 (1\leq k\leq K)应包含预计至少在 k 天。
约束
- 2\leq L\leq 10^9.
- 2 \leq N \leq 200\,000.
- 1 \leq K \leq 5.
- 0\leq X_i\leq L (1\leq i\leq N).
- 0\leq Y_i\leq L (1\leq i\leq N).
- 1 \leq Z_i\leq L (1\leq i\leq N).
- X_i+Y_i+Z_i\leq L (1\leq i\leq N).
- 所有输入值均为整数。
子任务
- (4 点) N = 2, K = 2.
- (5 点) L\leq 100, N\leq 100.
- (5 点) L\leq 1\,000.
- (7 点) N\leq 2\,000.
- (10 点) X_i = 0 (1\leq i\leq N), K = 1.
- (10 点) X_i = 0 (1\leq i\leq N).
- (23 点) K = 1.
- (18 点) K \leq 2.
- (18 点)没有额外的限制。
示例输入 1
5 2 2 1 0 3 0 1 4
示例输出 1
21 4
如果我们说明每个地区预计会下雨的天数,我们会得到下图。

此示例输入满足子任务的约束 1, 2, 3, 4, 8, 和 9.
示例输入 2
5 4 5 1 0 4 0 1 3 2 0 2 1 2 2
示例输出 2
21 10 2 0 0
如果我们说明每个地区预计会下雨的天数,我们会得到下图。

此示例输入满足子任务的约束 2, 3, 4, 和 9.