B. Best tests
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Geose is preparing another geometry problem. To complete his task, he needs to write the model solution and the test cases. Currently, he has a convex polygon $$$P$$$ with $$$n$$$ vertices, and he wants to generate additional tests using this polygon.

To create a new test, Geose selects a sub-polygon from $$$P$$$. A sub-polygon is defined as a polygon formed by a subsequence of at least $$$3$$$ vertices from the original polygon, without changing their order. In particular, the original polygon is also considered a sub-polygon.

Second example.

For example, in the figure above, the left polygon corresponds to the second sample, and all three polygons shown are valid sub-polygons of it.

Geose believes that the larger the area of a sub-polygon, the better the quality of the test. Since he is occupied with writing the solution for the problem, he asks for your help in designing the tests. Your task is to compute the areas of all possible sub-polygons of $$$P$$$ and print them in non-increasing order.

If the number of sub-polygons exceeds $$$2\cdot10^5$$$, only print the largest $$$2\cdot10^5$$$ areas, sorted in non-increasing order.

Input

The first line contains $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$).

Each of the following lines contains the coordinates $$$x$$$ and $$$y$$$ of the vertices ($$$0 \leq x,y \leq 10^9$$$). The vertices are given in anticlockwise order. The given polygon is guaranteed to be convex.

Output

In the first line print a single integer $$$m$$$ – the number of found areas. If there are less than $$$2\cdot10^5$$$ sub-polygons, $$$m$$$ must equal the total number of sub-polygons. Otherwise, $$$m=2\cdot10^5$$$.

The second line must contain $$$m$$$ real numbers with exactly one digit after the decimal point – the found areas in non-increasing order. The areas should be printed without any precision error.

Examples
Input
4
0 0
2 0
2 2
0 2
Output
5
4.0 2.0 2.0 2.0 2.0
Input
6
4 1
8 4
6 7
4 8
1 6
1 3
Output
42
31.0 29.0 27.5 26.5 26.5 24.5 24.5
23.0 22.5 22.0 20.5 20.0 19.0 19.0
18.5 18.0 17.5 17.5 16.0 16.0 15.0
14.5 14.0 14.0 12.0 11.5 11.0 11.0
10.5 10.5 10.5 10.0 9.0 8.5 8.5 7.5
7.0 6.5 4.5 4.5 3.5 2.0
Note

The areas are printed in multiple lines in the second case for clarity, but you should print all of them in the second line of the output.