CF1012F Passports

Gleb 是 InnoPolis 著名的竞赛编程教师。他计划在不久的将来前往 $N$ 个编程集训营。每个集训营都在不同的国家举办。对于每一次旅行，Gleb 都需要为该国申请签证。 对于每次旅行，Gleb 已知三个整数：旅行的第一天编号 $s_{i}$，旅行持续的天数 $len_{i}$，以及该国领事馆处理签证申请并将签证贴在护照上的所需天数 $t_{i}$。Gleb 有 $P$ 本有效护照（$1 \leq P \leq 2$），他可以自行决定将哪个签证贴在哪本护照上。 对于每次旅行，Gleb 会在第 $s_{i}$ 天的清晨飞往该国，并在第 $s_{i} + len_{i} - 1$ 天的晚上返回。 在第 $d$ 天申请签证时，Gleb 需要在这一天的中午待在 InnoPolis。因此，在旅行期间（包括第一天和最后一天），他无法申请签证。如果一趟旅行刚好在另一趟旅行的前一天结束，Gleb 也无法在两者之间申请签证。最早可以申请签证的时间是第 1 天。 在第 $d$ 天为第 $i$ 个国家申请签证后，Gleb 会在第 $d + t_{i}$ 天的中午拿回护照。领事馆会使用快递服务，因此即使 Gleb 当天不在 InnoPolis，他也能拿回护照。如果他在当天在 InnoPolis，可以在拿回护照的同一天再次申请签证。 如果 Gleb 在第 $s_{i}$ 天早上没有一本贴有该国签证的护照（且护照不在其他国家的领事馆办理签证），他将无法开始这次旅行。 请帮助 Gleb 决定每个签证应该贴在哪本护照上，以及他应该在什么时候申请每个签证。

输入的第一行包含两个整数 $N$（$1 \leq N \leq 22$）和 $P$（$1 \leq P \leq 2$），分别表示旅行次数和 Gleb 拥有的护照数量。 接下来的 $N$ 行描述 Gleb 的每次旅行。每行包含三个正整数 $s_{i}$、$len_{i}$、$t_{i}$（$1 \leq s_{i}, len_{i}, t_{i} \leq 10^{9}$），分别表示旅行的第一天、旅行持续的天数以及该国领事馆处理签证所需的天数。保证任意两次旅行不会重叠。

如果无法及时获得所有签证，输出 “NO”（不含引号）。否则，输出 “YES”，并在接下来的 $N$ 行中描述每次旅行。对于每次旅行，首先输出 Gleb 应该将该国签证贴在哪本护照上，然后输出他应该在哪一天申请该签证。按照输入顺序输出每次旅行。天数从 1 开始编号，1 号天是最早可以申请签证的日子。护照编号从 1 到 $P$。 如果有多种可行方案，输出任意一种即可。

以下是输出为 “YES” 的示例说明。 时间轴上的每个格子代表一天。矩形表示旅行，每次旅行从早上开始，晚上结束。带斜角的矩形表示签证申请。每个国家的旅行和签证申请用相同颜色表示。 在有两本护照的示例中，时间轴上方的签证申请和旅行使用第一本护照，时间轴下方的使用第二本护照。 示例 1：  示例 2：  示例 3：  由 ChatGPT 4.1 翻译