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.

If the source gear cannot move, give this result, even if the source and target gears are not connected.

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

---

hide comments

	David: 2023-01-11 05:55:28 Awesome problem! Second AC Java solution.
	hodobox: 2017-08-13 03:35:36 Some samples from the contest: 2 0 0 100 0 300 200 2 -1 ------ 2 0 0 100 0 300 100 0 ---- 0 0 1 0 3 2 4 0 3 -1
	matematikaadit: 2016-05-06 09:02:45 can we have better formatting for this problem? like the original one here https://icpcarchive.ecs.baylor.edu/external/73/7379.pdf
	Ram: 2016-03-30 14:37:38 Finally.. AC :) Last edit: 2016-04-04 17:15:29
	Joshua Kirstein: 2016-03-30 07:34:42 Blue.Mary this is the correct assumption. I'm not the original author of the problem and therefore will not modify the problem statement. Thanks for taking note :)
	[Rampage] Blue.Mary: 2016-03-30 06:16:22 My AC program assumes the source gear is the first gear given in the input, and the target gear is the last gear given in the input.