Problem B
Coordinate Correction

Your friend Z has been planning a hike for you both for over a year now. Unfortunately at the last minute, Z came down with a terrible cold and is unable to go. Unlike Z, you aren’t an expert hiker and are worried about getting lost. Being the good friend he is, Z has made you a GPS route. A route consists of a series of waypoints (GPS coordinates) with the intent that you go from each to the next in a straight line. However, as you approach the trailhead, you notice an issue with your GPS! It can only route you from one waypoint to the next if they are within $d$ kilometers of each other, otherwise it refuses to provide any assistance! Luckily, you have a plan! Before setting off, you will look through the waypoints and if any are more than $d$ kilometers away from the previous, you will add one or more new waypoints between them. To make it simple for yourself, you decide to evenly space the new waypoints between the two existing waypoints. Your GPS also has limited space so you will always add the minimum number of additional waypoints necessary. For example, if you have two waypoints $(0.0, 0.0)$ and $(10.0, 0.0)$ and $d = 3.0$, to make the route valid you will need to add at least three waypoints, so you would add waypoints at $(2.5, 0.0)$, $(5.0, 0.0)$, and $(7.5, 0.0)$.

Figure 1: The example from above. The original waypoints are shown in black and the newly added waypoints in white.

Can you write a program to go through Z’s route and correct it so that it will work for your GPS?

Input

The first line of input contains 2 integers $n$ ($3 \leq n \leq 100$) and $d$ ($1 \leq d \leq 100$), the number of waypoints in Z’s route and the maximum distance each waypoint can be from the previous in kilometers while working on your GPS. The next $n$ lines each contain two real numbers $x_i$ and $y_i$ ($-100.0000 \leq x_i, y_i \leq 100.0000$) each with $4$ digits after the decimal, the X and Y coordinates of the $i$th waypoint Z has placed in kilometers.

Output

For each waypoint in your corrected route, print one line with two real numbers $x_j$ and $y_j$, the X and Y coordinates of the $j$th waypoint in your corrected route. Your output will be considered correct if the absolute error of each coordinate is at most $10^{-4}$.

2 8
0.0000 0.0000
10.0000 0.0000

0.0 0.0
5.0 0.0
10.0 0.0

2 10
0.0000 0.0000
10.0000 10.0000

0.0 0.0
5.0 5.0
10.0 10.0

3 5
0.0000 0.0000
3.0000 3.0000
3.0000 20.0000

0.0 0.0
3.0 3.0
3.0 7.25
3.0 11.5
3.0 15.75
3.0 20.0