Bajtazar is celebrating his birthday today. $k$ guests have arrived for the party, and Bajtazar has prepared a huge cake. Now it needs to be divided!

Bajtazar has a square table with a side length of $10^6$ bajtometers, on which he has marked a coordinate system. The bottom-left corner of the table has coordinates $(0, 0)$, and the top-right corner has coordinates $(10^6, 10^6)$. Bajtazar placed the cake on the table. It turns out that the cake is in the shape of a simple polygon with integer coordinates, and each side of the cake is parallel to one of the edges of the table.

Bajtazar will make $k$ cuts to divide the cake into $k+1$ (not necessarily connected) pieces of equal area. He will make the cuts in a rather spectacular way: he has mounted a very powerful laser in the bottom-left corner of the table. Initially, the laser is off and points towards the point $(1, 0)$. Then, Bajtazar will slowly rotate the laser counter-clockwise. During this process, a display attached to the laser will indicate the point towards which the laser is pointing. This point is always exactly 1 bajtometer away from the bottom-left corner of the table. Thus, at the beginning of the rotation, the laser points to the point $(1, 0)$, after a 45-degree rotation it points to $(\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2})$, and after another 45-degree rotation it points to $(0, 1)$.

During this process, Bajtazar will turn on the laser $k$ times. The laser turns on for a very short moment and instantly cuts the cake along the line passing through the bottom-left corner of the table and the point towards which the laser is currently pointing. After each activation of the laser, one (not necessarily connected) piece of the cake is cut off, which the next guest will put on their plate. After $k$ cuts, the remaining $(k+1)$-th piece of the cake will be eaten by Bajtazar himself.

Bajtazar has a problem: when should he turn on the laser so that all guests (and he himself) receive the same amount of cake? Help him and indicate at what display readings he should turn on the laser.

Input

The first line of the input contains two integers $n$ and $k$ ($4 \le n \le 300\,000$, $2 \mid n$, $1 \le k \le 300\,000$) — the number of sides of the cake and the number of guests who came to the party, respectively. The vertices of the cake are numbered sequentially (along the perimeter) from 1 to $n$. The next $n$ lines contain the description of the cake; the $i$-th of these lines contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le 10^6$) representing the coordinates of the $i$-th vertex of the cake.

You can assume that each side of the cake is parallel to one of the coordinate axes and every two consecutive sides in the description of the cake are perpendicular. Furthermore, the polygon describing the cake is a simple polygon (i.e., no two vertices of the polygon are located at the same point, and two sides of the polygon have a common point only if they have a common vertex).

Output

The output should consist of $k$ lines. The $i$-th line should contain two real numbers $p_i$ and $q_i$ — the coordinates of the point $(p_i, q_i)$ towards which the laser should point during the $i$-th cut of the cake. The answer will be considered correct if both coordinates differ from the correct ones by at most $10^{-6}$. The numbers should be printed with at least 1 and at most 20 digits after the decimal point; scientific notation is not allowed.

Note: We suggest using the long double type in C++ to represent the result.

Examples

Input 1

6 3
2 2
9 2
9 4
4 4
4 9
2 9

Output 1

0.894427190999916 0.447213595499958
0.707106781186548 0.707106781186548
0.447213595499958 0.894427190999916

Note 1

Explanation of the example: The required coordinates are $(\frac{2\sqrt{5}}{5}, \frac{\sqrt{5}}{5})$, $(\frac{\sqrt{2}}{2}, \frac{\sqrt{2}}{2})$, $(\frac{\sqrt{5}}{5}, \frac{2\sqrt{5}}{5})$, and the lines passing through them are $y = \frac{1}{2}x$, $y = x$, $y = 2x$ (see figure). The area of each piece of cake is equal to 6 square bajtometers.

Subtasks