Visa Application Planning

Gleb, a renowned programming teacher from Innopolis, is planning to attend n coding camps held in different countries. For the i^th camp he knows the departure day \(s_i\), the duration \(len_i\) (so that the camp lasts from day \(s_i\) morning to day \(s_i+len_i-1\) evening), and the processing time \(t_i\) needed to obtain a visa in that country. He owns \(P\) valid passports and must decide which passport to use when applying for each country’s visa.

On any day \(d\) that Gleb applies for a visa he must be in Innopolis at noon. Consequently, he cannot apply on any day when he is traveling for a camp (even the first or the last day of a camp). In particular, if one camp ends and the next one starts immediately the next day, no visa application can be scheduled between them. The earliest day available for a visa application is day 1.

When Gleb applies for the visa for camp \(i\) on day \(d\), he will receive the country’s passport on day \(d+t_i\) at noon (even if he is not in Innopolis at that time). However, note that the passport used for the application must not be at the embassy at the time of applying. In order for Gleb to participate in camp i, he must have the corresponding passport in his possession by the morning of day \(s_i\). That is, if he applies on day \(d\) then it must hold that:

\(d + t_i < s_i\).

Furthermore, although Gleb has \(P\) passports (which can be used in a pipeline fashion), he as a person can only apply for one visa per day. If a passport is used in an application on day \(d\), it will be unavailable for any further application until it is returned on day \(d+t_i\) at noon ― so it can only be used on days strictly after \(d+t_i\).

Your task is to help Gleb by providing a visa application plan. The plan must assign each training camp an application day and a passport (numbered from 1 to \(P\)) such that:

• The chosen application day \(d\) is not during any camp (i.e. not in any interval \([s_j, s_j+len_j-1]\) for any camp \(j\)).
• For camp \(i\), \(d\) satisfies \(d + t_i < s_i\) (so that the passport is returned before the camp’s departure in the morning).
• No two applications occur on the same day (since Gleb can only make one visa application per day).
• If a passport is used for a visa application on day \(d\) with processing time \(t_i\), then it cannot be used again until day \(d+t_i+1\) or later.

If a valid plan exists, output YES followed by the plan. Otherwise, output NO. If a plan exists, for each camp (in the input order) output two integers: the chosen application day and the passport number used.

inputFormat

The input begins with two integers \(n\) and \(P\) (the number of camps and the number of passports). Each of the following \(n\) lines contains three integers \(s_i\), \(len_i\), and \(t_i\) describing a camp.

It is guaranteed that all input values are positive integers.

outputFormat

If a valid visa application plan exists, print YES on the first line. Then print \(n\) lines; the \(i^th</i> of these lines (corresponding to the \(i^th</i> camp in input order) should contain two integers: the chosen visa application day and the passport number used. If no valid plan exists, print NO.

sample

1 1
10 3 2

YES
1 1