Desert Bomb Defusal

A secret organization is conducting a military exercise in the desert. The objective of the exercise is to defuse a hidden bomb. The first phase of the exercise is a parachute drop. Soldiers jump from a hovering helicopter in a given order, and each lands at a predetermined point.

Each soldier has a survival radius. If the bomb is at a distance less than or equal to a soldier's survival radius from his landing point, that soldier will sacrifice himself to detonate the bomb. The commander wants to deploy as few soldiers as possible while guaranteeing that, in the worst-case scenario, at least one soldier survives.

The desert is represented as an infinite plane, and each soldier's landing point is given by coordinates \((x,y)\). The survival radius is denoted by \(r\). The soldiers' information is given in the order they jump. By the time the \(i\)th soldier lands, the previous \(i-1\) soldiers have already landed.

Your task is to read the soldiers' data from standard input and output the minimum number of soldiers that need to be deployed so that no matter where the bomb is placed, there will always be at least one soldier who survives. In other words, if the bomb is placed in any position \(p\), it should not be inside every soldier's survival circle among the deployed ones. If even deploying all soldiers still leaves a point that is inside every survival circle, output -1.

Note: A soldier's survival circle is defined as the closed disk centered at \((x,y)\) with radius \(r\). The problem reduces to finding the smallest prefix of soldiers for which the intersection of all their circles is empty.

inputFormat

The first line contains a single integer \(n\) (the number of soldiers). Each of the next \(n\) lines contains three numbers \(x\), \(y\), and \(r\), where \((x,y)\) is the landing coordinate of a soldier and \(r\) is his survival radius. The soldiers are given in the order they jump.

All numbers are real numbers.

outputFormat

Output a single integer, the minimum number of soldiers to deploy so that no matter where the bomb is placed, at least one soldier survives. If even deploying all \(n\) soldiers does not guarantee a survivor, output -1.

sample

3
0 0 5
4 0 2
10 0 1

3