Problem G. Gunman

Author:Georgiy Korneev (original idea), Roman Elizarov (text)   Time limit:2 sec
Input file:gunman.in   Memory limit:64 Mb
Output file:gunman.out  

Statement

Consider a 3D scene with OXYZ coordinate system. Axis OX points to the right, axis OY points up, and axis OZ points away from you. There is a number of rectangular windows on the scene. The plane of each window is parallel to OXY, its sides are parallel to OX and OY. All windows are situated at different depths on the scene (different coordinates z > 0).

A gunman with a rifle moves along OX axis (y = 0 and z = 0). He can shoot a bullet in a straight line. His goal is to shoot a single bullet through all the windows. Just touching a window edge is enough.

Your task is to determine how to make such shot.

Input file format

The first line of the input file contains a single integer number n  — the number of windows on the scene. The following n lines describe the windows. Each line contains five integer numbers x1i, y1i, x2i, y2i, zi. Here (x1i, y1i, zi) are coordinates of the bottom left corner of the window, and (x2i, y2i, zi) are coordinates of the top right corner of the window (x1i < x2i, y1i < y2i). Windows are ordered by z coordinate (zi > zi-1 for 2 ≤ i ≤ n).

Output file format

Output a single word 'UNSOLVABLE' if the gunman cannot reach the goal of shooting a bullet through all the windows. Otherwise, on the first line output a word 'SOLUTION'. On the next line output x coordinate of the point from which the gunman must fire a bullet. On the following n lines output x, y, z coordinates of the points where the bullet goes through the consecutive windows. All coordinates in the output file must be printed with six digits after decimal point.

Constraints

2 ≤ n ≤ 100; 0 < x1i, y1i, x2i, y2i, zi < 1000

Sample tests

No. Input file (gunman.in) Output file (gunman.out)
1
3
1 3 5 5 3
1 2 5 7 5
5 2 7 6 6
SOLUTION
-1.000000
2.000000 3.000000 3.000000
4.000000 5.000000 5.000000
5.000000 6.000000 6.000000
2
3
2 1 5 4 1
3 5 6 8 2
4 3 8 6 4
UNSOLVABLE

0.073s 0.010s 13