Migrated from Lutece 2949 葬花：暗黑桃花源

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

本题解法:CDQ分治

“晋太元中，武陵人捕鱼为业。缘溪行，忘路之远近。忽逢桃花林......” 千年来，无数旅人迷途山中，想找寻那传说中的世外桃源。 他们或流连忘返，或辞去后不复得路，或寻病而终。 在他们传颂于世的描述中：这里似乎是一个至臻至美的乌托邦。 可若是这乌托邦永恒不变，又何尝不是另一种形态的地狱？ 埋葬于历史尘埃中的呼钺国，掌握着千古一帝求之不得的长生不老秘术——代价又是什么？ 桃花落尽枯骨香，彼岸花开越千年。 留守其中的九百魂灵，渴望着“葬花之人”的到来。 白昼的她，想和你去看外面的世界，看那阔别千年的车水马龙。 夜晚的她，期许你将这一切彻底地埋葬.....

从 $1$ 年 $1$ 月 $1$ 日开始，桃花源的历史经过了整整 $k$ 年。其中，每年都有 $k$ 个月，每月都有 $k$ 天。

历史上发生了 $n$ 个重要事件，如果事件 $i$ 发生在 $x$ 年 $y$ 月 $z$ 日，则定义事件 $i$ 的重要度 $g(i)$ 为发生在 $1\sim x$ 年、$1\sim y$ 月、$1\sim z$ 日的事件的个数（不包含自身）。

对于 $t = 0,1,2,...,n-1$，分别求出使得 $g(i)=t$ 的 $i$ 的数量。

Input

第一行两个正整数 $n,k$ ，含义如题目所示。 接下来 $n$ 行， 第 $i$ 行三个正整数 $x_i, y_i, z_i$, 表示事件 $i$ 的年、月、日。

Output

共 $n$ 行，第 $t+1$ 行表示满足 $g(i)=t$ 的 $i$ 的数量。

Samples

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

3
1
3
0
1
0
1
0
0
1

Constraints

$1\le n \le 10^5, 1\le x_i,y_i,z_i \le k \le 2 \times 10^5$

Resources

2023 UESTC ICPC Training for Data Structures