Bessie and her fellow herd-mates have become extremely territorial. The n cows conveniently numbered 1..n have all staked out a grazing spot in the pasture. Each cow i has a spot on an integer grid (xi,yi) and an integer radius ri that indicates the circle she is staking out.

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.

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

Input

First line contains a single integer n (1 ≤ n ≤ 400). Each of the next n lines contains three integers: xi, yi (0 ≤ xi ≤ 10000, 0 ≤ yi ≤ 10000) and ri (1 ≤ ri ≤ 500).

Output

Print n lines. Line i contains a single integer that is the number of other fields that overlap with cow i's field.