题目描述

Gleb 是来自 Innopolis 的著名编程老师，他计划接下来参加 $n$ 场编程训练营。每场训练营会在不同的国家举办。他要申请每个国家的签证。

对于第 $i$ 场训练营，Gleb 知道出发日期 $s_i$，持续时长 $len_i$，和在该国申请签证需要的时间 $t_i$。Gleb 有 $P$ 本有效的护照并且他需要决定用哪本护照来申请签证。

第 $i$ 场训练营 Gleb 将在第 $s_i$ 天早上出发，在第 $s_i+len_i-1$ 天傍晚返回。

如果要在第 $d$ 天申请签证，Gleb 当天中午必须在 Innopolis。这意味着 Gleb 在参加训练营期间不能申请签证，包括第一天和最后一天。如果一场训练营结束后紧接着 Gleb 要去参加第二场训练营，他也无法在此期间申请签证。Gleb 最早可以申请签证的时间是第 $1$ 天。

在第 $d$ 天申请完第 $i$ 个国家的签证后，Gleb 会在第 $d+t_i$ 天中午获得该国的护照（即使当天 Gleb 不在 Innopolis）。

如果第 $s_i$ 天早上 Gleb 没有相应国家的护照，他就无法参加第 $i$ 场训练营。注意，当时护照不能在办理签证的使馆里面。

请你帮助 Gleb 找到一种申请签证的方案，使他可以顺利参加所有的训练营。

输入格式

输入第一行两个整数 $n,P$，分别表示训练营的个数和 Gleb 拥有的护照的个数。

接下来 $n$ 行，每行三个整数 $s_i,len_i,t_i$，表示第 $i$ 场训练营的开始时间，持续时长和对应国家办理签证所需时间。

保证每场都不相交。

输出格式

本题存在 Special Judge。

如果没有方案使得 Gleb 参加所有训练营，只用输出 NO。

否则，第一行输出 YES。

接下来输出 $n$ 行，每行两个整数分别表示对于每个训练营 Gleb 申请该国签证所用的护照的编号和他申请签证的日期。

输出顺序需要与输入顺序一致。日期从 $1$ 开始编号，护照编号 $1\cdots P$。

2 1
3 1 1
6 1 1

YES
1 1
1 4

3 1
13 2 2
7 3 1
19 3 4

YES
1 10
1 1
1 2

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

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

3 1
7 3 1
13 2 3
19 3 4

NO

提示

【样例解释】

样例一解释

每个单元格代表一天。矩形代表某一次训练营，从某一天早上开始，在某一天晚上结束。带角的矩形某一次申请签证的过程，从某一天中午开始，在某一天中午结束。一场训练营与他对应的申请签证的过程颜色相同。

样例二解释

样例三解释

上面代表第一个护照，下面代表第二个护照。

---

【数据规模与约定】

本题采用多测试点捆绑测试，共 9 个子任务。

• Subtask 1（5 pts）：$n\leq 2$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等，$P=1$；
• Subtask 2（8 pts）：$n\leq 10$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等，$P=1$；
• Subtask 3（7 pts）：$n\leq 10$，$s_i,len_i,t_i\leq 100$，所有 $t_i$ 均相等；
• Subtask 4（12 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 100$，$P=1$；
• Subtask 5（13 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 100$；
• Subtask 6（15 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 10^7$，$P=1$；
• Subtask 7（15 pts）：$n\leq 16$，$s_i,len_i,t_i\leq 10^7$；
• Subtask 8（15 pts）：$n\leq 20$；
• Subtask 9（10 pts）：无特殊限制。

对于全部的测试点，保证 $1\leq n\leq 22$，$1\leq P\leq 2$，$1\leq s_i,len_i,t_i\leq 10^9$。

---

来源：eJOI2018 Problem B「Passports」。

说明：翻译自翻。