AT_joi2026final_g 三角形降雨 (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 $ .  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,\ldots,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,\ldots,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. ---

### Subtasks 1. ( $ 4 $ points) $ N = 2 $ , $ K = 2 $ . 2. ( $ 5 $ points) $ L\leq 100 $ , $ N\leq 100 $ . 3. ( $ 5 $ points) $ L\leq 1\,000 $ . 4. ( $ 7 $ points) $ N\leq 2\,000 $ . 5. ( $ 10 $ points) $ X_i = 0 $ ( $ 1\leq i\leq N $ ), $ K = 1 $ . 6. ( $ 10 $ points) $ X_i = 0 $ ( $ 1\leq i\leq N $ ). 7. ( $ 23 $ points) $ K = 1 $ . 8. ( $ 18 $ points) $ K \leq 2 $ . 9. ( $ 18 $ points) There are no additional constraints. --- ### Sample Explanation 1 If we illustrate, for each region, the number of days on which rain is forecast to fall, we obtain the following figure.  This sample input satisfies the constraints for Subtasks $ 1, 2, 3, 4, 8, $ and $ 9 $ . --- ### Sample Explanation 2 If we illustrate, for each region, the number of days on which rain is forecast to fall, we obtain the following figure.  This sample input satisfies the constraints for Subtasks $ 2, 3, 4, $ and $ 9 $ . ### Constraints - $ 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 $ ). - All input values are integers.