$N$ jujutsu sorcerers are on a battlefield which can be represented by a line with $K$ regions. Each sorcerer uses their domain expansion, with the $i^{th}$ sorcerer's domain expansion covering and controlling all regions from $l_i$ to $r_i$, inclusive, and having strength $s_i$. It is guaranteed that no two sorcerer's domain expansions have the same strength. If a region is covered by two or more domain expansions, it will be controlled by the strongest one.

How many regions are controlled by each jujutsu sorcerer's domain expansion?

Constraints

$1\le N\le 5\times {10}^5$

$1\le K\le {10}^9$

$1\le l_i\le r_i\le K$

$1\le s_i\le {10}^9$

All values of $s_i$ are unique.

Subtask 1 [2/15]

$1\le N,K\le 100$

Subtask 2 [4/15]

$1\le N\le 3\times {10}^3$

Subtask 3 [4/15]

$1\le K\le {10}^6$

Subtask 4 [5/15]

No additional constraints.

Input Specification

The first line of input contains $N$ and $K$, representing the number of people and the number of regions.

The next $N$ lines of input each contain $l_i,r_i,s_i$, representing the range covered by the $i^{th}$ sorcerer's domain expansion and its strength.

Output Specification

Output $N$ space separated integers, with the $i^{th}$ integer representing how many regions the $i^{th}$ sorcerer's domain expansion controls.

Sample Input 1

2 5
1 3 1
3 5 2

Sample Output 1

2 3

Explanation for Sample Output 1

The first sorcerer's domain expansion covers regions $1,2,3$. The second sorcerer's domain expansion covers regions $3,4,5$. Region $3$ is controlled by the second sorcerer's domain expansion as it is stronger.

Sample Input 2

4 10
1 5 1
1 1 100
3 4 2
7 10 3

Sample Output 2

2 1 2 4