CF1012F.Passports

Gleb is a famous competitive programming teacher from Innopolis. He is planning a trip to N programming camps in the nearest future. Each camp will be held in a different country. For each of them, Gleb needs to apply for a visa.

For each of these trips Gleb knows three integers: the number of the first day of the trip s__i, the length of the trip in days len__i, and the number of days t__i this country's consulate will take to process a visa application and stick a visa in a passport. Gleb has P (1 ≤ P ≤ 2) valid passports and is able to decide which visa he wants to put in which passport.

For each trip, Gleb will have a flight to that country early in the morning of the day s__i and will return back late in the evening of the day s__i + len__i - 1.

To apply for a visa on the day d, Gleb needs to be in Innopolis in the middle of this day. So he can't apply for a visa while he is on a trip, including the first and the last days. If a trip starts the next day after the end of the other one, Gleb can't apply for a visa between them as well. The earliest Gleb can apply for a visa is day 1.

After applying for a visa of country i on day d, Gleb will get his passport back in the middle of the day d + t__i. Consulates use delivery services, so Gleb can get his passport back even if he is not in Innopolis on this day. Gleb can apply for another visa on the same day he received his passport back, if he is in Innopolis this day.

Gleb will not be able to start his trip on day s__i if he doesn't has a passport with a visa for the corresponding country in the morning of day s__i. In particular, the passport should not be in another country's consulate for visa processing.

Help Gleb to decide which visas he needs to receive in which passport, and when he should apply for each visa.

格列布是来自因诺波利斯的一位著名编程竞赛培训教师。他计划在近期前往 N 个编程训练营，每个训练营将在不同国家举办。对于每个训练营，格列布都需要申请该国的签证。

对于每次出行，格列布已知三个整数：出行起始日 s__i、出行持续天数 len__i，以及该国使领馆处理签证申请并完成贴签所需天数 t__i。格列布持有 P（1 ≤ P ≤ 2）本有效的护照，并可自主决定将哪国签证贴在哪本护照上。

每次出行中，格列布将于第 s__i 天清晨乘飞机出发，并于第 s__i + len__i − 1 天傍晚返回。

格列布若要在第 d 天申请签证，则必须在当天正午时分身处因诺波利斯。因此，他在任何出行期间（包括出行首日与末日）均无法申请签证。若某次出行在另一次出行结束后的次日即开始，格列布同样无法在两次出行之间申请签证。格列布最早可在第 1 天申请签证。

若格列布于第 d 天为第 i 国申请签证，则他将在第 d + t__i 天正午时分取回该本护照。各使领馆使用快递服务，因此即使格列布当天不在因诺波利斯，也能收到护照。若格列布在取回护照当天身处因诺波利斯，则他可于当天立即申请另一国签证。

若格列布在第 s__i 天清晨出发前，其任一护照中尚未包含对应国家的有效签证，或该护照正被其他国家使领馆用于签证处理，则他将无法按计划于第 s__i 天启程。

请帮助格列布确定：每本护照应贴哪些国家的签证，以及每份签证应于何时申请。

In the first line of the input there are two integers N (1 ≤ N ≤ 22) and P (1 ≤ P ≤ 2)—the number of trips and the number of passports Gleb has, respectively.

The next N lines describe Gleb's trips. Each line contains three positive integers s__i, len__i, t__i (1 ≤ s__i, len__i, t__i ≤ 109)—the first day of the trip, the length of the trip and number of days the consulate of this country needs to process a visa application. It is guaranteed that no two trips intersect.

输入的第一行包含两个整数 $N$（$1 \leq N \leq 22$）和 $P$（$1 \leq P \leq 2$），分别表示 Gleb 的旅行次数以及他所拥有的护照数量。

接下来的 $N$ 行描述 Gleb 的每次旅行。每行包含三个正整数 $s_i$、$len_i$、$t_i$（$1 \leq s_i,\ len_i,\ t_i \leq 10^9$），分别表示该次旅行的起始日期、旅行时长，以及该国领事馆处理签证申请所需的天数。保证任意两次旅行的时间区间互不相交。

If it is impossible to get all visas on time, just print "NO" (quotes for clarity). Otherwise, print "YES" and N lines describing trips. For each trip, first print number of the passport Gleb should put this country's visa in, and then print number of the day he should apply for it. Print trips in the same order as they appear in the input. Days are numbered from 1, starting with tomorrow—the first day you can apply for a visa. Passports are numbered from 1 to P.

If there are several possible answers, print any of them.

如果无法及时获得所有签证，则仅输出 "NO"（引号仅为清晰起见）。否则，输出 "YES"，然后输出 N 行描述行程。对于每一段行程，首先输出格列布应将该国签证放入的护照编号，然后输出他应申请该签证的日期编号。行程的输出顺序需与输入中出现的顺序一致。日期编号从 1 开始，其中第 1 天为明天（即最早可申请签证的日期）。护照编号从 1 到 P。

若存在多种可能的答案，输出任意一种即可。

Examples with answer "YES" are depicted below.

Each cell of the stripe represents a single day. Rectangles represent trips, each trip starts in the morning and ends in the evening. Rectangles with angled corners represent visa applications. Each application starts in the middle of a day and ends t__i days after. The trip and the visa application for the same country have the same color.

In examples with two passports, visa applications and trips depicted above the time stripe are made using the first passport, visa applications and trips depicted below the time stripe are made using the second passport.

Example 1:

Example 2:

Example 3:

答案为“YES”的示例如下所示。

时间条中的每个格子代表一天。矩形表示旅行，每次旅行均始于早晨、终于傍晚。带斜角的矩形表示签证申请，每次申请始于某天中午，并于 t__i 天后结束。同一国家的旅行与签证申请使用相同颜色。

在涉及两本护照的示例中，位于时间条上方绘制的签证申请与旅行使用第一本护照，位于时间条下方绘制的签证申请与旅行使用第二本护照。

示例 1：

示例 2：

示例 3：