Gleb 是一位来自 Innopolis 的著名竞赛编程教练。他计划在不久的将来前往 $N$ 个编程营地。每个营地将在不同的国家举行。对于每一个营地，Gleb 都需要申请签证。

对于这些行程中的每一次，Gleb 都知道三个整数：行程的第一天 $s_i$，行程持续的天数 $len_i$，以及该国领事馆处理签证申请并将其贴在护照上所需的天数 $t_i$。Gleb 拥有 $P$ ($1 \le P \le 2$) 本有效护照，他可以决定将哪份签证放入哪本护照中。

对于每次行程，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$ 天的清晨没有一本贴有相应国家签证的护照，他将无法开始他的行程。特别地，护照此时不应在另一个国家的领事馆进行签证处理。

请帮助 Gleb 决定他需要将哪些签证放入哪本护照，以及他应该在何时申请每份签证。

输入格式

输入的第一行包含两个整数 $N$ ($1 \le N \le 22$) 和 $P$ ($1 \le P \le 2$)，分别表示行程的数量和 Gleb 拥有的护照数量。

接下来的 $N$ 行描述了 Gleb 的行程。每行包含三个正整数 $s_i, len_i, t_i$ ($1 \le s_i, len_i, t_i \le 10^9$)，分别表示行程的第一天、行程长度以及该国领事馆处理签证申请所需的天数。保证任意两个行程互不重叠。

输出格式

如果无法按时获得所有签证，请直接打印 “NO”（不含引号）。否则，打印 “YES” 以及描述行程的 $N$ 行内容。对于每次行程，首先打印 Gleb 应将该国签证放入的护照编号，然后打印他应该申请该签证的日期。请按照行程在输入中出现的顺序打印。日期从 1 开始编号，从明天（即你可以申请签证的第一天）算起。护照编号为 1 到 $P$。

子任务

1. $N \le 2, s_i, len_i, t_i \le 100, t_i = t_j, P = 1$ (5 分)
2. $N \le 10, s_i, len_i, t_i \le 100, t_i = t_j, P = 1$ (8 分)
3. $N \le 10, s_i, len_i, t_i \le 100, t_i = t_j$ (7 分)
4. $N \le 16, s_i, len_i, t_i \le 100, P = 1$ (12 分)
5. $N \le 16, s_i, len_i, t_i \le 100$ (13 分)
6. $N \le 18, s_i, len_i, t_i \le 10^7, P = 1$ (15 分)
7. $N \le 18, s_i, len_i, t_i \le 10^7$ (15 分)
8. $N \le 20$ (15 分)
9. $N \le 22$ (10 分)

样例

输入 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

说明

答案为 “YES” 的样例已在下方描绘。

时间轴上的每个单元格代表一天。矩形代表行程，每个行程在清晨开始，在深夜结束。带有斜角的矩形代表签证申请。每个申请在某天的中午开始，并在 $t_i$ 天后结束。同一国家的行程和签证申请具有相同的颜色。

在拥有两本护照的样例中，时间轴上方描绘的签证申请和行程是使用第一本护照完成的，时间轴下方描绘的签证申请和行程是使用第二本护照完成的。