Description

有n朵花，每朵花有三个属性：花形(s)、颜色(c)、气味(m)，又三个整数表示。现要对每朵花评级，一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽，当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然，两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

Input

第一行为N,K (1 <= N <= 100,000, 1 <= K <= 200,000 ), 分别表示花的数量和最大属性值。

以下N行，每行三个整数si, ci, mi (1 <= si, ci, mi <= K)，表示第i朵花的属性

Output

包含N行，分别表示评级为0...N-1的每级花的数量。

Sample Input

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

Sample Output

3

1

3

0

1

0

1

0

0

1

HINT

 

1 <= N <= 100,000, 1 <= K <= 200,000

 

三维偏序集，黄学长告诉我们可以

1.树状数组+treap √

2.cdq分治

目前只会树套树的做法，然而我的树套树真心很弱

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define M 5000005 6 using namespace std; 7 int n,m,sz,tmp; 8 int root[200005],ans[100005],sum[100005]; 9 int size[M],ls[M],rs[M],v[M],w[M],rnd[M];10 struct node{
    int a,b,c;}a[100005];11 int lowbit(int x){
    return x&(-x);}12 bool cmp(node a,node b){13     if (a.a==b.a&&a.b==b.b) return (a.c
          
           num){ins(ls[k],num);if (rnd[ls[k]]
           
            num) getrank(l,num);33 else if (v[k]