Problem Description

Gleb is a renowned programming teacher from Innopolis, and he plans to attend $n$ programming camps in the coming period. Each camp will be held in a different country, and he needs to apply for a visa for each country.

For the $i$-th camp, Gleb knows the departure date $s_i$, the duration $len_i$, and the time $t_i$ required to obtain a visa in that country. Gleb has $P$ valid passports and needs to decide which passport to use for each visa application.

Gleb will depart for the $i$-th camp on the morning of the $s_i$-th day and return on the evening of the $(s_i + len_i - 1)$-th day.

To apply for a visa on the $d$-th day, Gleb must be in Innopolis at noon that day. This means Gleb cannot apply for a visa during a camp, including the first and last days. If a camp ends and Gleb immediately departs for another camp, he cannot apply for a visa during this period. The earliest day Gleb can apply for a visa is the 1st day.

After applying for the visa of the $i$-th country on the $d$-th day, Gleb will receive the passport at noon on the $(d + t_i)$-th day (even if he is not in Innopolis that day).

If Gleb does not have the corresponding country's passport by the morning of the $s_i$-th day, he cannot attend the $i$-th camp. Note that the passport cannot be at the visa application office.

Help Gleb find a scheme to apply for visas so that he can attend all the camps.

Input Format

The first line of input contains two integers $n$ and $P$, representing the number of camps and the number of passports Gleb has, respectively.

The next $n$ lines each contain three integers $s_i$, $len_i$, and $t_i$, representing the start date, duration, and visa processing time for the $i$-th camp, respectively.

It is guaranteed that no two camps overlap.

Output Format

This problem has a Special Judge.

If there is no scheme that allows Gleb to attend all camps, output NO.

Otherwise, output YES on the first line.

The next $n$ lines should each contain two integers representing the passport number Gleb uses to apply for the visa of each country and the date he applies for the visa.

The output order should be consistent with the input order. Dates are numbered starting from 1, and passport numbers range from 1 to $P$.

Sample Input and Output

Sample Input #1

2 1
3 1 1
6 1 1

Sample Output #1

YES
1 1
1 4

Sample Input #2

3 1
13 2 2
7 3 1
19 3 4

Sample Output #2

YES
1 10
1 1
1 2

Sample Input #3

7 2
15 1 1
14 1 1
18 1 1
21 1 1
9 4 6
22 2 5
5 4 3

Sample Output #3

YES
2 13
1 1
1 16
1 19
1 2
2 16
2 1

Sample Input #4

3 1
7 3 1
13 2 3
19 3 4

Sample Output #4

NO

Notes/Hints

Data Constraints

This problem uses multiple test cases bundled into subtasks, with a total of 9 subtasks.

• Subtask 1 (5 pts): $n \leq 2$, $s_i, len_i, t_i \leq 100$, all $t_i$ are equal, $P = 1$;
• Subtask 2 (8 pts): $n \leq 10$, $s_i, len_i, t_i \leq 100$, all $t_i$ are equal, $P = 1$;
• Subtask 3 (7 pts): $n \leq 10$, $s_i, len_i, t_i \leq 100$, all $t_i$ are equal;
• Subtask 4 (12 pts): $n \leq 16$, $s_i, len_i, t_i \leq 100$, $P = 1$;
• Subtask 5 (13 pts): $n \leq 16$, $s_i, len_i, t_i \leq 100$;
• Subtask 6 (15 pts): $n \leq 16$, $s_i, len_i, t_i \leq 10^7$, $P = 1$;
• Subtask 7 (15 pts): $n \leq 16$, $s_i, len_i, t_i \leq 10^7$;
• Subtask 8 (15 pts): $n \leq 20$;
• Subtask 9 (10 pts): No special restrictions.

For all test cases, it is guaranteed that $1 \leq n \leq 22$, $1 \leq P \leq 2$, $1 \leq s_i, len_i, t_i \leq 10^9$.

Source: eJOI2018 Problem B "Passports".

Note: Translated from the original.

见题面 Input 部分

见题面 Output 部分