Description

There are $n$ elements. The $i$-th element has three attributes $a_i, b_i, c_i$. Let $f(i)$ be the number of $j$ such that $a_j \leq a_i$, $b_j \leq b_i$, $c_j \leq c_i$, and $j \ne i$.

For all $d \in [0, n)$, find the number of $i$ such that $f(i) = d$.

Input Format

The first line contains two integers $n,k$, denoting the number of elements and the maximum attribute value.

The next $n$ lines each contain three integers $a_i ,b_i,c_i$, representing the three attribute values.

Output Format

Output $n$ lines. The $d + 1$-th line contains the number of $i$ such that $f(i) = d$.

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

Hint

For all testdata, it is guaranteed that $1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5$.

Translated by ChatGPT 5