402809: GYM100886 D Catenary

D. Catenarytime limit per test1 secondmemory limit per test256 mebibytesinputstandard inputoutputstandard output

Everyone has seen something like this a lot of times:

Have you ever thought about the curve formed by a hanging chain? No, it is not a parabola, it is a graph of the hyperbolic cosine, called a catenary. In this problem, you have to draw a graph of some discrete analog of the catenary.

Suppose that you have several rods connected by their ends in a line in a certain order. The connections are non-stretchable and flexible, that is, each two successive rods can join at any angle. The rods are very thin, so they can be treated as line segments. The mass is uniformly distributed along each segment. Moreover, all the segments have the same density, so their masses are proportional to their lengths.

The ends of this chain are fixed at the points (0, 0) and (L, 0), and the segments form a polyline due to gravity. The force of gravity, as well as the y-axis, is directed downwards. Determine the form of the resulting polyline.Input

The first line contains two integers n and L (3 ≤ n ≤ 10, 200 ≤ L ≤ 299). The second line contains n integers l₁, l₂, ..., l_n (100 ≤ l_i ≤ 199), the lengths of the segments from left to right. It is not allowed to change the order of the segments.

Output

Output n - 1 lines. Each line must contain two real numbers, presenting x and y-coordinates of the points of the polyline from left to right. Do not output the first and the last points (0, 0) and (L, 0).

Please print the numbers with at least three digits after the decimal point.

ExamplesInput

3 200
100 100 100

Output

50.0000000000 86.6025403784
150.0000000000 86.6025403784

Input

3 241
128 105 108

Output

76.2967704600 102.7754971643
180.4447346423 89.4262815813