Bitocja is a vast country with $n$ cities, numbered from 1 to $n$. Bitocja lies on a Cartesian coordinate plane. City $i$ has coordinates $(x_i, y_i)$, and no two cities are located at the same point.

A large number of cities is, of course, associated with a strong and well-managed state, but not everyone is equally happy about this. Bitomir, the newly elected chancellor, has been tasked with planning a traditional holiday parade that would visit all the cities and return to the starting point. However, Bitomir does not have as much public support as he would like – if he does not choose the order of cities such that the parade route has an optimal (the smallest possible) length, citizens will complain about the waste of public funds. Finding such an optimal route (generally known as the Traveling Salesperson Problem, which is classified as an NP-hard problem) requires enormous computing power, so when the King of Bitocja learned the number and cost of the computers required, he quickly agreed to reduce the scale of this year's parade.

It was decided that the parade will visit only $k$ out of the $n$ cities. Bitomir has a free hand in choosing the cities (he can tell the citizens that these are the cities with the richest culture and history), but among the chosen cities, he must propose an order of visitation that is optimal, meaning the total length of the route must be the smallest among the $k!$ possibilities.

Can you help Bitomir? Formally, you must choose $k$ from the given $n$ points and list them in a certain order. Let the total length of your route be $A$. If the checker program finds an order of the points you listed such that the total length is less than $A \cdot (1 - 10^{-9})$, you will receive a Wrong Answer verdict on that test. The total length of a route with cities $P_1, P_2, \dots, P_k$ is the sum of $k$ Euclidean distances:

$$d(P_1, P_2) + d(P_2, P_3) + \dots + d(P_{k-1}, P_k) + d(P_k, P_1)$$

where the Euclidean distance between points $P_a(x_a, y_a)$ and $P_b(x_b, y_b)$ is:

$$d(P_a, P_b) = \sqrt{(x_a - x_b)^2 + (y_a - y_b)^2}$$

Do not worry if three cities lie on a straight line and the route between two of them happens to pass through the third – in that case, the parade will simply bypass it by using the numerous bridges and overpasses in Bitocja.

Input

The first line of input contains two integers $n$ and $k$ ($n = 300\,000, k = 500$) – the number of cities in Bitocja and the number of cities the parade is to visit. Note: the sample test in the problem description does not meet these conditions and is not included in the system tests (submitted solutions will not be run against it).

The next $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^8 \le x_i, y_i \le 10^8$) – the coordinates of the $i$-th city. For $i \neq j$, it holds that $x_i \neq x_j$ or $y_i \neq y_j$.

Output

Print $k$ lines, each with two integers $x_i, y_i$, separated by a space – the coordinates of the next city on the parade route. No city may be repeated. Print any of the correct solutions.

Examples

Input 1

6 4
-10 -10
-10 10
10 -10
50 10
10 10
48 10

Output 1

-10 10
48 10
50 10
-10 -10

Note 1

The $k = 4$ listed cities give a total length of:

$$\sqrt{58^2 + 0^2} + \sqrt{2^2 + 0^2} + \sqrt{60^2 + 20^2} + \sqrt{0^2 + 20^2} \approx 143.246$$

No order of visiting these four cities gives a smaller total length, so the printed output is one of the correct solutions. We remind you that this sample test is not included in the tests on SIO.