Problem M: Settler

Problem

二次元平面上にN個の空き地がある。空き地にはそれぞれ1からNまでの番号が割り振られている。どの空き地もとても小さいので、点とみなすことができる。i番目の空き地は(x_i,y_i)に存在している。

太郎君はこのN個の空き地の中からちょうどK個を選び、それらの空き地に建物を建てることにした。 しかし、あまりにも近い場所に複数の建物を建てても面白くないと思ったので、太郎君はそれぞれの空き地どうしのユークリッド距離が必ず2以上となるように空き地を選ぶことにした。

太郎君が選ぶ空き地の組み合わせとして考えられるものを出力するプログラムを作成せよ。 組み合わせが複数存在する場合は、辞書順で最小のものを出力せよ。 ただし、どのようにK個の空き地を選んだとしても、いずれか2つの空き地のユークリッド距離が2より小さくなってしまう場合は、かわりに-1を出力せよ。

Input

入力は以下の形式で与えられる。

N K
x1 y1
x2 y2
...
xN yN

Constraints

入力は以下の条件を満たす。

• 入力は全て整数である。
• 2 ≤ K ≤ N ≤ 6,000
• 1 ≤ x_i , y_i ≤ 1,000,000 ( 1 ≤ i ≤ N )
• x_i mod 2 = floor ( y_i ÷ 2 ) mod 2 ( 1 ≤ i ≤ N )
  (ここでfloor ( y_i ÷ 2 ) とはy_iを2で割り小数点以下を切り捨てた値である)
• 同じ座標に複数の空き地が存在することはない。

Output

太郎君が選ぶ空き地の番号を昇順に1行ずつ出力せよ。

Sample Input 1

3 2
2 1
1 2
1 3

Sample Output 1

1
3

Sample Input 2

4 3
2 1
1 2
1 3
2 4

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

2
3
4

Note

Link

 

---