Kevin has set up ~N~ lamps for a festival lasting ~M~ days. Each lamp may change colour once during the festival. Every colour is represented by an integer from ~1~ to ~N~.

For each lamp ~i~:

• On days ~1,2,\dots,D_i-1~, its colour is ~A_i~.
• On days ~D_i,D_i+1,\dots,M~, its colour is ~B_i~.

If ~D_i=1~, the lamp has colour ~B_i~ for the entire festival. The two colours ~A_i~ and ~B_i~ may be equal, in which case the lamp does not visibly change colour.

For each day of the festival, determine the number of distinct colours displayed by the lamps.

Input

The first line contains two integers ~N~ and ~M~ (~1 \leq N,M \leq 3\times10^5~): the number of lamps and the number of days in the festival.

Each of the next ~N~ lines contains three integers ~A_i~, ~D_i~, and ~B_i~ (~1 \leq A_i,B_i \leq N~, ~1 \leq D_i \leq M~), describing the colours and change day of lamp ~i~.

Output

Output ~M~ lines. On line ~j~, output the number of distinct colours displayed on day ~j~.

Example 1

Input 1

6 7
1 3 2
2 6 5
5 5 1
3 3 5
4 1 6
6 3 6

Output 1

5
5
3
3
4
4
4

The lamps display the following colours each day: