(In memory of Eoin Curran.)

During the last wild party at home, Masao was unable to host so many models, as his house was too small. Therefore, he has decided to move and start celebrating parties somewhere else. To do so, he has hired an architect to build a new house for him.

The house has a convex polygon shape. The architect, however, is a bit clumsy and messes up the map of the house. Instead of giving Masao the coordinates of the vertices of the polygon, he gives him the location of the midpoints of the sides. After thinking for a while, Masao realizes that, with that information, it is not always possible to recover the original map of the house: there might be one, zero, or even an infinity of solutions consistent with the given points. Please help Masao to recover the original information, when possible.

**Input**

Input consists of several cases,
each one with the number of vertices 3 ≤ *v* ≤ 10^{5},
followed by 2*v* real numbers,
the (*x*,*y*) coordinates of the midpoints, in counterclockwise order.

**Output**

For every case, print “`NO SOLUTION`” or “`INFINITE SOLUTIONS`”
in case there are zero or infinite solutions, respectively.
If there is exactly one solution
(it will always be convex, you do not have to check it),
print the vertices in counterclockwise order and one per line,
with four digits after the decimal point,
and followed by a line with 10 dashes.
Print the vertices starting
with the first vertex of the side of the first midpoint.
The input cases have no precision issues.

Public test cases

**Input**

4 0 0 0 1 1 1 1 0 3 0.2 0.5 1.2 1.5 0.2 1.5 4 0 0 0 1 1 1 3 3

**Output**

INFINITE SOLUTIONS -0.8000 0.5000 1.2000 0.5000 1.2000 2.5000 ---------- NO SOLUTION

Information

- Author
- Javier Gómez
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Vuitè Concurs de Programació de la UPC - Final
- Date
- 2010-09-22