Problem

There are $ n $ bombs on a two-dimensional plane. Each bomb is numbered from 1 to $ n $, and the $ i $ th bomb is located at coordinates $ (x_i, y_i) $.
It is known that all bombs have the same Manhattan distance from the origin.
When the $ i $ th bomb explodes, the bombs that are within $ r_i $ in Manhattan from the coordinates $ (x_i, y_i) $ will also explode in a chain reaction.
For each $ n $ bomb, find the number of bombs that will remain unexploded if only that bomb is ignited.

Constraints

The input satisfies the following conditions.

• $ 2 $ ≤ $ n $ ≤ $2 \ times 10 ^ 5$
• $ -10 ^ 9 $ ≤ $ x_i, y_i $ ≤ $ 10 ^ 9 $
• $ 1 $ ≤ $ r_i $ ≤ $ 10 ^ 9 $
• $ | x_i | + | y_i | = | x_j | + | y_j | $$ (1 ≤ i, j ≤ n) $
• There can never be more than one bomb at the same coordinates

Input

$ n $
$ x_1 $ $ y_1 $ $ r_1 $
$ x_2 $ $ y_2 $ $ r_2 $
...
$ x_n $ $ y_n $ $ r_n $

All inputs are given as integers.
The number of bombs $ n $ is given on the first line. Of the following $ n $ lines, the $ i $ line is given $ x_i, y_i, r_i $, which represents the information of the $ i $ th bomb, separated by blanks.

Output

On the $ i $ line, output the number of bombs that remain without exploding if only the $ i $ th bomb is ignited.

Examples

Input

2
-1 -1 10
1 1 1

Output

0
1

Input

3
3 2 2
4 -1 4
1 -4 7

Output

2
1
0

见题面

见题面