19040번 - Labeled Points 다국어

문제

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.

제한

힌트