Note: This problem is missing data.

A school has organized a popular "Sunshine Long-Distance Running" activity. To "work healthily for the motherland for fifty years," students have left their dorms, classrooms, and laboratories to participate in a 3000-meter run on the playground. For a time, the playground was bustling with activity, crowded with people, and presented an unprecedented spectacle.

To encourage students to run, the physical education department created "Sunshine Running Cards" and required students to swipe their cards to prove the distance they covered. To prevent students from taking shortcuts, the department set up many card-swiping points along the track, requiring students to swipe them in order. To prevent students from swiping cards for each other, the department arranged for a teacher to supervise on-site. However, the teacher's field of vision is limited and may not be able to monitor all the card-swiping points. To solve this problem, the teachers from the physical education department have come to you for help.

Briefly, we can treat the track as a circle centered at the origin with radius $r$. The supervising teacher stands at the origin, and their field of vision is a given $n$-sided polygon, where the vertices are ordered by polar angle with respect to the origin. You are asked to place $m$ equidistant card-swiping points on the track such that as many card-swiping points as possible fall within the teacher's field of vision (the field of vision includes the boundary of the polygon).

Input

The first line contains two positive integers $n$, $m$ and a positive real number $r$, the meanings of which are detailed in the problem description.

The following $n$ lines describe the polygon. Each line contains two real numbers $x$ and $y$, representing the coordinates of a vertex on the polygon. The vertices are given in counter-clockwise order.

Output

Please output $m$ lines, each containing two real numbers $x$ and $y$ (separated by a space), representing the coordinates of a card-swiping point. It is recommended to output with 15 significant digits.

Scoring

For each test case, we will first check if your output solution is valid. A valid solution must satisfy the following two points:

1. The relative error between the distance of each card-swiping point to the origin and $r$ must not exceed $10^{-10}$.
2. The relative error between the distance between two adjacent card-swiping points and $a$ must not exceed $10^{-9}$, where $a$ is the side length of a regular $m$-sided polygon inscribed in a circle of radius $r$.

If your solution is valid, we will count the number of card-swiping points in your solution that fall within the teacher's field of vision, denoted as $yourans$. We have set 10 scoring parameters $a_1 \leq a_2 \leq \cdots \leq a_{10}$. If $yourans \geq a_i$, your score is $i$. (If multiple conditions are met, the highest score is taken.)

Specifically, if your solution is invalid, we will select the point described in the first line of your output file, denoted as $P$. Then, we will select a point $Q$ on the ray $OP$ such that $|OQ|=r$. Next, we will rotate $Q$ around the origin to generate a valid solution, which will be treated as your solution and scored according to the rules above, but your score will be reduced by 2 points (down to a minimum of 0; it will not become negative).

Examples

Input 1

7 6 1.3
1 0
2 1
2 2
1 1.0000000001
-1 1
-1.5 -1
0 -0.5

Output 1

1.27136243102707 0.27136243102707
0.40067445661139 1.23671337820012
-0.87068797441569 0.96535094717305
-1.27136243102707 -0.27136243102708
-0.40067445661138 -1.23671337820012
0.87068797441569 -0.96535094717304

Constraints

For $60\%$ of the data, $n, m \leq 5\,000$;

For $100\%$ of the data, $3 \leq n, m \leq 100\,000$, $1 \leq r \leq 3$.