考虑笛卡尔平面上的 $N$ 个点。这些点分别被标记为从 $1$ 到 $N$ 的正整数。 这些点具有特殊性质：对于每个点 $(x_i, y_i)$，其坐标均为正整数，且满足等式 $x_i \pmod 2 = \lfloor y_i/2 \rfloor \pmod 2$。

你的任务是从这些点中选择一个包含 $K$ 个点的序列，使得该序列中任意两点之间的距离不小于 $2$。在所有满足条件的序列中，找出点标签序列字典序最小的那一个。

输入格式

第一行包含两个整数 $N$ 和 $K$ ($2 \le K \le N \le 6000$)。接下来的 $N$ 行，每行包含一个点的坐标：两个整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le 10^9$, $x_i \pmod 2 = \lfloor y_i/2 \rfloor \pmod 2$)。

保证所有给定的点互不相同。

输出格式

如果无法选择 $K$ 个点使得任意两点间的距离不小于 $2$，输出 $-1$。否则，输出 $K$ 个整数，每行一个，表示字典序最小的满足条件的点标签序列。

样例

样例输入 1

3 2
2 1
1 2
1 3

样例输出 1

1
3

样例输入 2

4 3
2 1
1 2
1 3
2 4

样例输出 2

-1

样例输入 3

5 3
5 7
5 6
6 8
20 20
4 8

样例输出 3

2
3
4