시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB17000.000%

## 문제

Consider $N$ points on the Cartesian plane. The points are labeled with positive integers from $1$ to $N$. The points are special: for each point $(x_i, y_i)$, the coordinates are positive integers, and the equality $x_i \bmod 2 = \lfloor y_i / 2 \rfloor \bmod 2$ holds.

Your task is to select a sequence of $K$ of those points with the following property: the distance between every pair of points from this sequence is not less than $2$. Among all such sequences, find the one for which the sequence of the points' labels is lexicographically minimal.

## 입력

The first line of input contains two integers $N$ and $K$ ($2 \le K \le N \le 6000$). Each of the next $N$ lines contains coordinates of a point: two integers $x_i$ and $y_i$  ($1 \le x_i, y_i \le 10^9$, $x_i \bmod 2 = \lfloor y_i / 2 \rfloor \bmod 2$).

It is guaranteed that all given points are pairwise distinct.

## 출력

If it is impossible to select $K$ points so that the distance between every pair of them is not less than $2$, print $-1$. Otherwise, print $K$ integers, one integer per line: the sequence with the desired property which is lexicographically minimal.

## 예제 입력 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