题目描述

JOI 国是一个边长为 $L$ 的正三角形，其顶点为点 $A, B$ 和 $C$。这里 $L$ 是一个正整数。边 $AB$ 在东西方向上连接顶点 $A$ 和 $B$，顶点 $A$ 是 JOI 国最西端的一点，而顶点 $B$ 是最东端的一点。顶点 $C$ 是 JOI 国最北端的一点。

JOI 国被划分为 $L^2$ 个区域，每个区域都是一个边长为 $1$ 的正三角形。作为某个区域顶点的点被称为格点。对于满足 $0 \leq y \leq L$ 且 $0 \leq x \leq L-y$ 的整数 $x, y$，从南数第 $(1+y)$ 个、从西数第 $(1+x)$ 个的格点记作 $(x, y)$。特别地，$A, B$ 和 $C$ 分别记作 $(0,0), (L, 0)$ 和 $(0, L)$。例如，下图显示了 $L=5$ 时的区域和格点。

::::align{center} ::::

在 JOI 国，已经公布了未来 $N$ 天的天气预报。在第 $i$ 天，预报降雨将落在以格点 $(X_i, Y_i), (X_i + Z_i, Y_i)$ 和 $(X_i, Y_i + Z_i)$ 为顶点的三角形区域 $T_i$ 内。如果一个区域完整地包含在 $T_i$ 中，则称该区域在第 $i$ 天被预报有雨。

为了应对降雨引起的灾害，有必要针对每个 $k = 1, 2, \dots, K$，确定预报有至少 $k$ 天降雨的区域数量。

给定 JOI 国的大小、天气预报以及 $K$，请编写一个程序，对于每个 $k = 1, 2, \dots, 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$ 天降雨的区域数量。

5 2 2
1 0 3
0 1 4

21
4

5 4 5
1 0 4
0 1 3
2 0 2
1 2 2

21
10
2
0
0

提示

样例 1

如果我们图示每个区域预报有雨的天数，将得到下图。

::::align{center} ::::

该样例输入满足子任务 $1, 2, 3, 4, 8$ 和 $9$ 的限制条件。

样例 2

如果我们图示每个区域预报有雨的天数，将得到下图。

::::align{center} ::::

该样例输入满足子任务 $2, 3, 4$ 和 $9$ 的限制条件。

限制条件

• $2 \leq L \leq 10^{9}$。
• $2 \leq N \leq 200000$。
• $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$)。
• 所有输入值均为整数。

子任务

1. (4 分) $N = 2, K = 2$。
2. (5 分) $L \le 100, N \le 100$。
3. (5 分) $L \le 1\,000$。
4. (7 分) $N \le 2\,000$。
5. (10 分) $X_i = 0$ $(1 \le i \le N), K = 1$。
6. (10 分) $X_i = 0$ $(1 \le i \le N)$。
7. (23 分) $K = 1$。
8. (18 分) $K \le 2$。
9. (18 分) 无额外限制。