题目描述

本题译自 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$ 进行编号。

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

数据范围与提示

所有数据均满足：$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 分）：无特殊限制。