2814 「eJOI2018」护照

本题译自 eJOI2018 Problem B. Passports

Gleb 是来自 Innopolis 的著名算法竞赛教练，他计划在接下来一段时间参加 $N$ 场训练营。每场训练营都在不同的国家举行。为了能够参与这些训练营，他需要去申请相应国家的签证。

对于第 $i$ 场训练营，Gleb 知道如下信息：出发日期 $s_i$，持续时间 $len_i$ 和该国使馆申请签证花费的时间 $t_i$。Gleb 有 $G$ 本护照，他可以自己决定他用哪本护照来申请签证。

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

要在第 $d$ 天申请签证，Gleb 当天中午必须在 Innopolis，这意味着，他在参加训练营期间（包括第一天和最后一天）都无法申请签证。如果有一场训练营在前一场训练营结束后的第二天就开始，Gleb 也无法在这期间申请签证。Gleb 最早可以申请签证的时间是第 $1$ 天。

在第 $d$ 天申请第 $i$ 场训练营对应国家的签证后，Gleb 将在第 $d+t_i$ 天的中午取回护照，使馆提供护照邮寄服务，因此即使 Gleb 当天不在 Innopolis，他也能拿到护照。如果 Gleb 当天在 Innopolis，他可以在收到护照的同一天再次申请签证。

如果 Gleb 在第 $s_i$ 天的早上没有持有有相应国家签证的护照，他就无法参加第 $i$ 场训练营。特别注意的是，相应的护照必须在 Gleb 手中，而不是在办理签证的使馆那里。

现在请你帮助 Gleb 求出一种申请护照的方案，使得他可以顺利参加所有的训练营。

第一行两个整数 $N,P$，分别代表训练营的数量和 Gleb 拥有的护照的数量。

接下来 $N$ 行，每行三个正整数 $s_i,len_i,t_i$，分别代表第 $i$ 场训练营的开始日期，持续天数和相应国家使馆申请签证花费的时间。

保证任意两个行程都不相交。

如果不存在一种方案使得 Gleb 能顺利参加所有训练营，输出 NO。

否则，在第一行输出 YES，并在接下来 $N$ 行中描述 Gleb 的申请护照方案。

对于每场训练营，输出两个整数，第一个整数代表 Gleb 申请用的护照的编号，第二个整数代表 Gleb 申请护照的日期。

你输出的训练营的顺序应该和输入给出的顺序一致。日期从 $1$ 开始编号，护照从 $1\ldots P$ 进行编号。

本样例对应下图：

在该图（以及接下来两张图中），我们用一个单元格代表一天，矩形代表一次训练营，训练营从某一天早上开始，到某一天晚上结束，有角的矩形代表申请签证的过程，每次签证申请从某一天中午开始，到某一天中午结束。一场训练营和其相对应的签证申请采用相同的颜色。

在有两本护照的例子中，我们将使用第一本护照的行程和签证申请放在时间条上方，而将使用第二本护照的行程和签证申请放在时间条下方。

本样例对应下图：

本样例对应下图：

所有数据均满足：$1 \leq N \leq 22$，$1 \leq P \leq 2$，$1 \leq s_i,len_i,t_i \leq 10^9$。

各子任务的分值和约束条件如下：

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