Problem Description

The country of JOI is an equilateral triangle with side length $L$ whose vertices are points $A,B$, and $C$. Here, $L$ is a positive integer. Side $AB$ connects vertices $A$ and $B$ in the east-west direction, and vertex $A$ is the westernmost point of the country of JOI, while vertex $B$ is the easternmost point. Vertex $C$ is the northernmost point of the country of JOI.

The country of JOI is divided into $L^{2}$ regions, each of which is an equilateral triangle with side length $1$. A point that is a vertex of some region is called a lattice point. For integers $x,y$ satisfying $0 \leq y \leq L$ and $0 \leq x \leq L-y$, the lattice point that is the $(1 + y)$-st from the south and the $(1 + x)$-st from the west is denoted by $(x, y)$. In particular, $A,B$, and $C$ are denoted by $(0,0),(L, 0)$, and $(0, L)$, respectively. For example, the following figure shows the regions and the lattice points when $L = 5$.

::::aligned{center} ::::

In the country of JOI, weather forecasts for the next $N$ days have been announced. On day $i$, rain is forecast to fall in the triangular region $T_i$ whose vertices are lattice points $(X_i, Y_i),(X_i + Z_i, Y_i)$, and $(X_i, Y_i + Z_i)$. An region is said to be forecast to receive rain on day $i$ if the entire region is contained in $T_i$.

In order to prepare for disasters caused by rainfall, it is necessary to determine, for each $k = 1, 2, \dots, K$, the number of regions that are forecast to receive rain on at least $k$ days.

Given the size of the country of JOI, the weather forecasts, and $K$, write a program which, for each $k = 1, 2, \dots, K$, computes the number of regions that are forecast to receive rain on at least $k$ days.

Input Format

Input is given from Standard Input in the following format:

$L$ $N$ $K$
$X_1$ $Y_1$ $Z_1$
$X_2$ $Y_2$ $Z_2$
$\vdots$
$X_N$ $Y_N$ $Z_N$

Output Format

Print $K$ lines to Standard Output. The $k$-th line ($1 \leq k \leq K$) should contain the number of regions that are forecast to receive rain on at least $k$ days.

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

Hint

Sample 1

If we illustrate, for each region, the number of days on which rain is forecast to fall, we obtain the following figure.

::::aligned{center} ::::

This sample input satisfies the constraints for Subtasks $1$, $2$, $3$, $4$, $8$, and $9$.

Sample 2

If we illustrate, for each region, the number of days on which rain is forecast to fall, we obtain the following figure. ::::aligned{center} :::: This sample input satisfies the constraints for Subtasks $2$, $3$, $4$, and $9$.

Constraints

• $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$).
• All input values are integers.

Subtasks

1. (4 points) $N = 2$, $K = 2$.
2. (5 points) $L \le 100$, $N \le 100$.
3. (5 points) $L \le 1\,000$.
4. (7 points) $N \le 2\,000$.
5. (10 points) $X_i = 0$ $(1 \le i \le N)$, $K = 1$.
6. (10 points) $X_i = 0$ $(1 \le i \le N)$.
7. (23 points) $K = 1$.
8. (18 points) $K \le 2$.
9. (18 points) There are no additional constraints.