JOI 国是一个边长为 $L$ 的等边三角形，其顶点分别为 $A$、$B$ 和 $C$。其中，$L$ 是一个正整数。边 $AB$ 连接顶点 $A$ 和 $B$，方向为东西向，$A$ 是 JOI 国的最西端点，$B$ 是最东端点。顶点 $C$ 是 JOI 国的最北端点。

JOI 国被划分为 $L^2$ 个区域，每个区域都是边长为 1 的等边三角形。某个区域的顶点被称为格点。对于满足 $0 \le y \le L$ 和 $0 \le x \le L - y$ 的整数 $x, y$，从南向北数第 $(1 + y)$ 个、从西向东数第 $(1 + x)$ 个格点记为 $(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)$。如果一个区域完全包含在 $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 \le k \le K$）应包含预报有雨天数至少为 $k$ 天的区域数量。

数据范围

• $2 \le L \le 10^9$
• $2 \le N \le 200\,000$
• $1 \le K \le 5$
• $0 \le X_i \le L$ ($1 \le i \le N$)
• $0 \le Y_i \le L$ ($1 \le i \le N$)
• $1 \le Z_i \le L$ ($1 \le i \le N$)
• $X_i + Y_i + Z_i \le L$ ($1 \le i \le 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 分) 无附加限制

样例

输入格式 1

5 2 2
1 0 3
0 1 4

输出格式 1

21
4

说明 1

该样例输入满足子任务 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

该样例输入满足子任务 2、3、4 和 9 的限制。