← 返回题目列表

Codeforces · 1012/F

F. 护照

中文机器翻译题面 查看原题

Gleb是来自Innopolis的著名竞技编程老师。他计划在不久的将来去N个编程营旅行。每个训练营将在不同的国家举行。格莱布需要为他们每个人申请签证。

对于每一次旅行,Gleb 都知道三个整数:旅行第一天的数字 si、旅行长度(以天数 leni 为单位)以及该国领事馆处理签证申请并将签证贴在护照上所需的天数 ti。 Gleb 拥有 P (1 ≤ P ≤ 2) 份有效护照,并且能够决定他想要将哪种签证放入哪本护照中。

对于每次旅行,Gleb 将在 si 当天清晨飞往该国家/地区,并在 si + leni - 1 当天傍晚返回。

要申请 d 天的签证,Gleb 需要在这一天中午到达 Innopolis。所以他不能在旅行期间申请签证,包括第一天和最后几天。如果一次旅行在另一次旅行结束后的第二天开始,格列布也无法在两者之间申请签证。 Gleb 最早可以在第一天申请签证。

d天申请i国签证后,Gleb将在d + ti天中间取回护照。领事馆使用送货服务,因此即使格莱布当天不在伊诺波利斯,也可以取回护照。如果格莱布当天在伊诺波利斯,他可以在收到护照的同一天申请另一个签证。

如果Gleb在第si天早上没有持有相应国家签证的护照,他将无法在第si天开始他的旅行。特别是护照不应该在他国领事馆办理签证。

帮助格列布决定他需要用哪本护照获得哪些签证,以及他应该何时申请每个签证。

输入

输入的第一行有两个整数 N (1 ≤ N ≤ 22) 和 P (1 ≤ P ≤ 2)——分别是 Gleb 的旅行次数和护照数量。

接下来的 N 行描述了 Gleb 的旅行。每行包含三个正整数si,leni,ti(1≤si,leni,ti≤109)——旅行的第一天,旅行的长度以及该国领事馆处理签证申请所需的天数。保证两个行程不会相交。

输出

如果无法按时获得所有签证,只需打印“NO”(为了清楚起见,加引号)。否则,打印“YES”和 N 行描述行程。每次旅行,首先打印格列布应放入该国签证的护照号码,然后打印他应申请的日期。按照输入中出现的顺序打印行程。天数从 1 开始,从明天开始——您可以申请签证的第一天。护照编号从 1 到 P。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #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

注意

回答“是”的示例如下所示。

条带的每个单元格代表一天。矩形代表行程,每次行程从早上开始,到晚上结束。有角的矩形代表签证申请。每个申请都在一天的中间开始,并在几天后结束。同一国家的行程和签证申请颜色相同。

在具有两本护照的示例中,时间条上方所示的签证申请和旅行是使用第一本护照进行的,时间条下方所示的签证申请和旅行是使用第二本护照进行的。

示例 1:

示例 2:

示例 3: