Bajtazar is the owner of a newly opened gym. Because the competition in the market is high, he decided to take a professional approach to every aspect of his business and offer his clients an advanced reservation system.

The gym is equipped with $k$ different exercise machines. Each reservation consists of a client expressing a desire to use a specific machine for one hour within a time interval of their choosing. The system then determines the exact times when clients will use the machines so that no machine is assigned to two different reservations at the same time.

Bajtazar has already received all $n$ reservation requests for the near future. He rightly noticed that if at any given moment no one is using the gym, he can turn off the lights, turn off the air conditioning, and close the supplement bar. To save money, he would like to organize the exercises in such a way that the total number of hours during which at least one person is exercising in the gym is as small as possible. Help him with this task.

Input

The first line of input contains two integers $n$ and $k$ ($1 \le n \le 1\,000\,000$, $1 \le k \le 10^9$), representing the number of reservation requests and the number of machines in the gym, respectively. The machines are numbered with integers from $1$ to $k$; for simplicity, we also number the hours with consecutive integers starting from $1$.

The next $n$ lines describe the reservation requests: the $i$-th of these lines contains three integers $a_i$, $b_i$, and $p_i$ ($1 \le a_i \le b_i \le 10^9$, $1 \le p_i \le k$), representing the reservation of the $i$-th client, who expressed a desire to use machine $p_i$ for one hour in the time interval from hour $a_i$ to hour $b_i$ (inclusive).

Output

If it is possible to schedule the exercises so that all reservations are fulfilled and no machine is used by two people at the same time, you should output $n + 1$ lines. The first line should contain the minimum number of hours during which at least one person is exercising in the gym. In the $i$-th of the following $n$ lines, there should be an integer $t_i$ from the interval $[a_i, b_i]$ indicating that for the $i$-th reservation, machine $p_i$ is occupied at hour $t_i$.

If it is not possible to schedule the exercises according to the above requirements, you should output the word NIE.

Examples

Input 1

4 2
1 3 1
1 1 1
1 3 2
3 3 2

Output 1

2
3
1
1
3

Input 2

3 1
1 2 1
1 2 1
1 2 1

Output 2

NIE