K. Fragile Pinball
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a convex polygon with $$$n$$$ edges, there is a very small pinball, which can be seen as a point, that starts from a certain position inside or on the polygon and moves straight at a positive constant speed.

You can activate an edge of the convex polygon at any moment for an instant. If the pinball is exactly on an activated edge (including the endpoints) at that time, it will be reflected by this edge. That is, the angle of incidence equals the angle of reflection with respect to the line that the edge lies on. Since the edges are fragile, each edge can be activated at most once.

It is important to note that if the pinball is simultaneously on two edges, you cannot activate both edges at the same time. However, you can activate the two edges in quick succession. In this case, the pinball will be reflected twice, and the moving direction of the pinball also changes twice while its position and speed remain unchanged. You can also choose to activate only one of the edges or not to activate any.

Since the pinball is also fragile, it can only bear at most $$$k$$$ reflections. You need to find the maximum distance that the pinball can travel within the convex polygon for each $$$k = 0, 1, 2, \ldots, n$$$.

Input

The first line contains an integer $$$n$$$ ($$$3 \le n \le 6$$$), indicating the number of vertices of the convex polygon.

For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-100 \le x_i, y_i \le 100$$$), indicating the coordinates of the $$$i$$$-th vertex of the convex polygon.

It is guaranteed that the $$$n$$$ vertices are given in counter-clockwise order, and any three of them are not collinear.

Output

Output $$$(n+1)$$$ lines, the $$$i$$$-th of which contains a real number, indicating the length of the longest journey of the pinball with at most $$$i-1$$$ reflections.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally speaking, suppose that your output is $$$a$$$ and the jury's answer is $$$b$$$, your output is accepted if and only if $$$\frac{|a - b|}{\max(1, |b|)} \le 10^{-6}$$$.

Examples
Input
3
4 0
0 3
0 -1
Output
5.000000000000000000
8.000000000000000000
8.868185038797563409
12.210024810881955830
Input
3
4 0
0 3
0 2
Output
5.000000000000000000
5.366563145999495272
6.111919138499425171
6.782203304416628317
Note

The sample cases are shown in the figures below.