P15945 Triangular Rainfall

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 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$

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.

### 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.