Passports

题意翻译

你现在要进行 $n$（$n\le 22$）段旅行，第 $i$ 段旅行开始于第 $s_i$ 天的清晨，结束于第 $s_i+len_i-1$ 天的深夜，保证任意两个 $[s_i,s_i+len_i-1]$ 无交。 由于出国需要签证，现在要求在第 $i$ 个国家的旅行开始前（也就是第 $s_i$ 天之前）拿到第 $i$ 个国家的签证。你有 $P$ 个护照（$1\le P\le 2$），在任意一天 $T$ 的下午，**如果你此时此刻还在国内**，那么你可以选择一个国家 $i$ 并将任意一个现在在你手头上护照交给第 $i$ 个国家的领事会，假设你交的是你第 $j$ 个护照，那么你会在第 $T+t_i$ 天的上午收到带有第 $i$ 个国家签证的护照。这里有几个注意点： 1. 由于存在上午下午的时间先后关系，**因此你在某一天上午收到办理完签证的护照后，可以在下午直接拿着这个护照办理另一个国家的签证**。 2. 办理签证时，只要求开始办理的时候要求人在国内，如果结束办理的时候人在国外那么它会寄到家里，人回国之后即可带着它办理另一个国家的签证。但是假设你办理第 $i$ 个国家的签证时用的是第 $x_i$ 个护照，那么在 $[s_i,s_i+len_i-1]$ 这段区间内第 $x_i$ 个护照**必须不能处于办理状态**，反之第 $3-x_i$ 个护照则可以按照上述说法处于办理状态。 问是否存在一种方案使得对于任意一个国家，你都可以在开始这个国家的旅行之前收到这个国家的签证，如果可行还需输出 $n$ 行每行两个整数 $x_i,v_i$ 表示办理第 $i$ 个国家签证的护照和将护照交给第 $i$ 个国家领事会的时间（也就是开始办理的时间）

题目描述

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.

输入输出格式

输入格式

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}<=10^{9} $ )—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.

输出格式

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.

输入输出样例

输入样例 #1

2 1
3 1 1
6 1 1

输出样例 #1

YES
1 1
1 4

输入样例 #2

3 1
13 2 2
7 3 1
19 3 4

输出样例 #2

YES
1 10
1 1
1 2

输入样例 #3

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

输出样例 #3

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

输入样例 #4

3 1
7 3 1
13 2 3
19 3 4

输出样例 #4

NO

说明

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: