~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