Paintball

Time limit1sMemory limit128 MB

Summary

Decide whether a path can cross a 1000x1000 field from west edge to east edge while avoiding circular firing ranges, and give the northernmost entry and exit points.

Level: Medium6 of 10
Topics: Geometry, Union-find, Graph, Sorting
Solved: No attempts yet

Problem

You are playing paintball on a $1000 \times 1000$ square field. Several opponents are hiding behind trees at various positions on the field. Each opponent can fire a paintball a certain distance in any direction from where they stand. Can you cross the field to the far side without being hit by a paintball?

Input

Assume the southwest corner of the field is at $(0, 0)$ and the northwest corner at $(0, 1000)$ . The first line contains the number of opponents $n$ ( $n \le 1000$ ). Each of the next $n$ lines contains three real numbers describing one opponent: its location $(x, y)$ and its firing range. An opponent hits you if you ever pass within its firing range.

You must enter the field somewhere between the southwest and northwest corners (the west edge) and leave somewhere between the southeast and northeast corners (the east edge).

Output

If you can complete the trip, output four real numbers, each with two digits after the decimal point, separated by spaces: the coordinates at which you enter the field followed by the coordinates at which you leave it. If you can enter and leave at several places, give the most northerly. If there is no such pair of positions, print the single line:

IMPOSSIBLE

Examples2

Example 1

Input

3
500 500 499
0 0 999
1000 1000 200

Expected output

0.00 1000.00 1000.00 800.00

Example 2
Input
```
1
500 500 600
```
Expected output
```
IMPOSSIBLE
```