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: