Gears
A set of gears is installed on the plane. You are given the center coordinate and radius of each gear, which are all integer-valued. For a given source and target gear, indicate what happens to the target gear if you attempt to turn the source gear. Possibilities are:
- The source gear cannot move, because it would drive some gear in the arrangement to turn in both directions.
- The source gear can move, but it is not connected to the target gear.
- The source gear turns the target gear, at a certain ratio.
Input
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains a single integer n (1 ≤ n ≤ 1,000), the total number of gears. Following this will be n lines, one per gear, containing the x, y (-10,000 ≤ x, y ≤10,000) and r (1 ≤ r ≤ 10,000) values for the gear, where (x, y) is the position of the axle of the gear, and r is its radius. Assume that the teeth of the gears are properly designed, and accounted for in the radius, so that any gear will mesh with any other gear if (and only if) they are tangent to each other. The gears will never overlap.
Output
Output a single line, with the following content, based on the result:
- "-1" - if the source gear cannot move.
- "0" - if the source gear can move but is not connected to the target.
- "a b" - if the source gear moves the target gear, where a and b are two space-separated integers, and a : b is the ratio of source gear revolutions to target gear revolutions reduced to its lowest form (i.e. they have no common factor other than 1).
- a is always positive.
- If the target turns in the same direction as the source, b is positive.
- If the target turns in the opposite direction as the source, b is negative.
Example
Input: 16
10 10 5
20 10 5
30 10 5
40 10 5
10 20 5
20 20 5
30 20 5
40 20 5
10 30 5
20 30 5
30 30 5
40 30 5
10 40 5
20 40 5
30 40 5
40 40 5
Output: 1 1