我们将要建造一座新城市：大都市（Metropolis）。这座城市将建在一个无限大的方格网格上。建成后的城市将包含 $n$ 座摩天大楼，编号从 $1$ 到 $n$。每座摩天大楼将占据网格中不同的单元格。在施工过程中的任何时刻，当前不包含摩天大楼的单元格被称为空地。

给定 $n$ 座摩天大楼的计划坐标，你的任务是找到一种建造顺序，使其满足以下规则：

• 施工队只有一台起重机，因此大都市必须一次建造一座摩天大楼。
• 你建造的第一座摩天大楼可以是 $n$ 座计划摩天大楼中的任意一座。
• 后续每一座摩天大楼都必须与至少一座之前已建成的摩天大楼共享一条边或一个角（以便更容易地将新摩天大楼与网格对齐）。
• 在建造摩天大楼时，必须存在一条从大都市外部到达施工现场的路径，且该路径只能通过共享边的空地移动。换句话说，应该存在一条由共享边的空地组成的路径，将即将放置摩天大楼的单元格与某个满足 $|r| > 10^9$ 和/或 $|c| > 10^9$ 的单元格 $(r, c)$ 连接起来。

如果存在解，设摩天大楼的建造顺序为 $s_1, \dots, s_n$。子任务分为两类：

类型 1：你可以输出任何合法的顺序。 类型 2：你必须找到使 $s_n$ 最大的顺序。在此基础上，你必须找到使 $s_{n-1}$ 最大的顺序，以此类推。换句话说，你必须找到使序列 $(s_n, s_{n-1}, \dots, s_1)$ 字典序最大的合法建造顺序。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 150,000$)，表示摩天大楼的数量。 第二行包含一个整数 $t$ ($1 \le t \le 2$)，描述上述子任务的类型。 接下来 $n$ 行，第 $i$ 行包含两个空格分隔的整数 $r_i$ 和 $c_i$ ($|r_i|, |c_i| \le 10^9$)，表示包含第 $i$ 座摩天大楼的单元格坐标。

保证没有两座摩天大楼位于同一位置。

输出格式

如果无法按照给定的规则建造摩天大楼，请输出一行字符串 “NO”。 否则，输出 $n+1$ 行。第一行应包含字符串 “YES”。对于每个 $i$，剩余 $n$ 行中的第 $i$ 行应包含一个整数 $s_i$。

在 $t=1$ 的子任务中，如果存在多个合法的顺序，你可以输出其中任意一个。

子任务

子任务 1 (8 分)：$t = 1$ 且 $n \le 10$ 子任务 2 (14 分)：$t = 1$ 且 $n \le 200$ 子任务 3 (12 分)：$t = 1$ 且 $n \le 2,000$ 子任务 4 (17 分)：$t = 2$ 且 $n \le 2,000$ 子任务 5 (20 分)：$t = 1$ 子任务 6 (10 分)：$t = 2, n \le 70,000$ 且对于每个 $i$ 有 $|r_i|, |c_i| \le 900$ 子任务 7 (19 分)：$t = 2$

样例

样例输入 1

3
2
0 0
0 1
0 2

样例输出 1

YES
1
2
3

样例输入 2

3
1
0 0
1 1
2 2

样例输出 2

YES
2
3
1

样例输入 3

2
1
0 0
0 2

样例输出 3

NO

说明

在第一个样例中，有三座摩天大楼排成一行。它们始终都可以从大都市外部到达，并且有四种保持连通性的建造顺序： 1, 2, 3 2, 1, 3 2, 3, 1 3, 2, 1

由于 $t=2$，我们必须选择第一个选项。

在第二个样例中，与第一个样例唯一的区别是第 2 座摩天大楼仅与第 1 座和第 3 座摩天大楼共享角，与第一个样例相同的顺序集是合法的。由于 $t=1$，这些答案中的每一个都是正确的。

在第三个样例中，大都市是不连通的。显然我们无法建造它。