Migrated from Lutece 3124 尽力局

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

Tag：CDQ分治

队伍的比赛成绩很不好，若只兔头教练准备好好评估队员的实力。

现在队伍里共有 $n$ 位选手，为了便于量化实力，第 $i$ 位选手有 $a_i,b_i, c_i$ 三个属性，当选手 $A$ 的三项属性都不小于另一位选手 $B$ 时，我们称 $A$ 能胜过 $B$（五五开？五五开也是赢！）选手 $A$ 的巅峰值即他能胜过的选手数。

现在若只教练希望能统计处于各个巅峰值的选手个数，由于工头不可抗力的影响，这个艰巨的任务就交给你了！

简单来说: 设 $f(i)$ 表示同时满足 $a_j \le a_i,b_j\le b_i,c_j\le c_i$ 且 $j\neq i$ 的 $j$ 的数量。 对于 $d\in[0,n)$，求 $f(i)=d$ 的数量。

Input

第一行两个整数 $n, k$（$1 \le n,k\le 2\times 10^5$）表示队员数量和最大属性值。

接下来 $n$ 行，每行三个整数 $a_i , b_i , c_i$（$1 \le a_i,b_i,c_i\le k \le 2\times 10^5$）分别表示三个属性值。

Output

输出 $n$ 行，每行为 $f(i)=d$ 的数量。

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

Resources

2024 UESTC ICPC Training for Data Structure