Gears

Time limit4sMemory limit256 MB

Summary

Gears that touch drive each other in opposite directions at inverse radius ratios; report the reduced ratio of the last gear to the first, or a jam or no link.

Level: Medium5 of 10
Topics: Graph, BFS, Math
Solved: No attempts yet

Problem

A set of gears sits on the plane. Every gear has an integer center coordinate and an integer radius. Two gears mesh when they touch on the outside, that is, when the distance between their centers equals the sum of their radii.

Meshed gears turn in opposite directions, and the number of turns each one makes is inversely proportional to its radius. While a gear of radius $r_1$ makes one full turn, a meshed gear of radius $r_2$ makes $r_1/r_2$ turns.

Report what happens to the output gear when you try to turn the input gear. There are three possibilities.

The input gear cannot move at all, because turning it would drive some gear in two directions at once.
The input gear can move, but it is not connected to the output gear.
The input gear turns the output gear at a fixed ratio.

If the input gear cannot move, report that result even when the input gear and the output gear are not connected.

Input

The first line contains the number of gears $n$ ( $2 \le n \le 1000$ ).

Each of the next $n$ lines contains three space-separated integers $x_i$ , $y_i$ , and $r_i$ , the center coordinate and the radius of the $i$ -th gear ( $-10^4 \le x_i, y_i \le 10^4$ , $1 \le r_i \le 10^4$ ).

Assume the tooth count of every gear is high enough that meshed gears always engage correctly. No two gears overlap. The first gear in the list is the input gear and the last gear is the output gear.

Output

If the input gear cannot move, print The input gear cannot move. on a single line.

If the input gear can move but is not connected to the output gear, print The input gear is not connected to the output gear. on a single line.

Otherwise print, on a single line, the ratio of the output gear's rotation to the input gear's rotation in the form ##:##, reduced to lowest terms. Write the ratio as a negative ratio when the output gear turns in the direction opposite to the input gear. For example, if the output gear turns clockwise three times while the input gear turns counterclockwise twice, print -3:2.

Examples4

Example 1
Input
```
2
0 0 100
200 0 100
```
Expected output
```
-1:1
```
Example 2
Input
```
3
0 0 100
200 0 100
400 0 100
```
Expected output
```
1:1
```

Example 3

Input

Expected output

1:1

Example 4

Input

Expected output

The input gear cannot move.