#1811 Crop Circles

57  10 s   128 MB  

Description

Bessie and her fellow herd-mates have become extremely territorial. The $N$ $(1 \leq N \leq 400)$ cows conveniently numbered $1 \dots N$ have all staked out a grazing spot in the pasture. Each cow $i$ has a spot on an integer grid $(0 \leq X_i \leq 10,000; 0 \leq Y_i \leq 10,000)$ and an integer radius $R_i$ that indicates the circle she is staking out $(1 \leq R_i \leq 500)$.

The cows are a bit greedy and sometimes stake out territory of their herd-mates. For each cow, calculate the number of other cows whose territory overlaps her territory.

By way of example, consider these six cows with indicated locations and radii (don't confuse radius with diameter!):

By visual inspection, we can see and count the overlaps, as shown.

Input

Output

Sample Input

Sample Output

6
7 7 7
16 14 7
11 13 2
10 17 3
29 8 5
15 7 4
3
4
3
2
0
2

HINT

NOTE: the test data will avoid pathological situations like tangents where the circles just barely touch.