D. Parallel Lines
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Once upon a time, there were $$$k$$$ parallel lines in a two-dimensional plane and $$$n$$$ points on these lines. It is known that there were at least two points on each line.

Now you are given these $$$n$$$ points, and your task is to find those $$$k$$$ parallel lines.

Input

The first line contains two integers $$$n$$$, $$$k$$$ ($$$2\le n \le 10^4,1 \le k \le \mathrm{min}(50,\frac{n}{2})$$$), denoting the number of points and parallel lines.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$1\le x_i, y_i \le 10^9$$$), denoting the coordinates of the $$$i$$$-th point.

It is guaranteed that $$$n$$$ points are pairwise distinct (i.e. $$$\forall 1\le i \lt j \le n$$$, either $$$x_i \neq x_j$$$ or $$$y_i \neq y_j$$$ holds).

Output

The output contains $$$k$$$ lines.

In the $$$i$$$-th line, first output an integer $$$m_i$$$ ($$$2 \le m_i \le n$$$), denoting the number of points on the $$$i$$$-th parallel line. Then output $$$m_i$$$ integers $$$x_1,x_2,\ldots,x_{m_i}$$$, denoting the indices of points on the $$$i$$$-th line.

Your output should satisfy that each point appears and only appears on one line, and $$$k$$$ lines are parallel and different.

It is guaranteed there is a valid solution to distribute the $$$n$$$ points onto $$$k$$$ parallel lines. If multiple solutions exist, output any of them.

Example
Input
4 2
1 3
2 5
4 7
5 9
Output
2 3 4 
2 1 2