Busy Beaver 终于愤怒地退出了扫雷，转而玩起了《麻将连连看》（Mahjong Connect）。他在笛卡尔平面上的不同位置有 $N$ 张麻将牌。每张牌 $i$ 都有整数坐标 $(x_i, y_i)$ 和一个类型 $t_i$，其中 $1 \le t_i \le M$。

两张不同的牌 $i$ 和 $j$ 能够匹配，当且仅当满足以下所有条件：

• 它们具有相同的类型，即 $t_i = t_j$；
• 它们在同一行或同一列，即 $x_i = x_j$ 或 $y_i = y_j$；

• 它们没有被其他类型的牌阻挡，即在该行或该列中处于它们之间的所有牌（如果有的话）都具有相同的类型。形式化地：

  • 如果 $y_i = y_j$，那么对于满足 $y_k = y_i$ 且 $\min\{x_i, x_j\} < x_k < \max\{x_i, x_j\}$ 的每张牌 $k$，必须满足 $t_k = t_i$；
  • 如果 $x_i = x_j$，那么对于满足 $x_k = x_i$ 且 $\min\{y_i, y_j\} < y_k < \max\{y_i, y_j\}$ 的每张牌 $k$，必须满足 $t_k = t_i$。

完美匹配是指将这 $N$ 张牌划分为 $N/2$ 个互不相交的配对，使得根据上述规则，每一对都是有效的匹配。判断是否存在完美匹配。如果存在，输出任意一个完美匹配；否则，报告不存在完美匹配。

输入格式

第一行包含两个整数 $N$ 和 $M$（$2 \le N \le 3 \cdot 10^5$，$1 \le M \le 3 \cdot 10^5$，$N$ 为偶数）。

接下来的 $N$ 行描述这些牌。其中第 $i$ 行包含三个整数 $x_i$、$y_i$ 和 $t_i$（$|x_i|, |y_i| \le 10^9$，$1 \le t_i \le M$）。

保证所有点对 $(x_i, y_i)$ 互不相同。

输出格式

如果不存在完美匹配，输出单行 NO。

否则，输出单行 YES。然后输出 $N/2$ 行，每行包含两个整数 $i$ 和 $j$（$1 \le i, j \le N$ 且 $i \ne j$），表示牌 $i$ 和牌 $j$ 组成一个匹配对。

每个从 $1$ 到 $N$ 的索引必须恰好出现一次。这些配对可以以任意顺序输出，且在每个配对中，$i$ 和 $j$ 的顺序无关紧要。

你可以以任何大小写形式输出答案。例如，字符串 yEs、yes、Yes 和 YES 都会被识别为肯定回答。

样例

输入样例 1

4 2
-1 0 1
1 0 1
0 -1 2
0 1 2

输出样例 1

YES
1 2
3 4

输入样例 2

4 2
-1 0 1
1 0 1
0 0 2
0 1 2

输出样例 2

NO

输入样例 3

22 3
1 1 2
1 2 2
1 3 2
1 4 1
2 3 2
3 2 1
3 1 2
4 3 2
5 4 1
5 3 1
5 2 1
5 1 1
7 1 3
7 2 3
7 3 3
7 4 3
9 4 3
10 4 3
11 4 3
10 3 1
10 2 1
10 1 3

输出样例 3

YES
1 7
2 3
4 9
5 8
6 11
10 12
13 22
14 15
16 17
18 19
20 21

说明

在第一个样例中，我们可以分别将位于 $(-1, 0), (1, 0)$ 和 $(0, -1), (0, 1)$ 的牌进行配对。

在第二个样例中，我们无法进行相同的操作，因为位于 $(0, 0)$ 的牌阻挡了 $(-1, 0)$ 和 $(1, 0)$ 之间的连接。

第三个样例的视觉化效果如下（不同的颜色代表不同类型的牌）：

再次注意，如果答案为 YES，任何顺序的任何有效配对都将被接受。例如，对于第一个样例，以下输出也是可以接受的：

YES
4 3
1 2