Problem M: Manhattan Bomb

Problem

2次元平面上に$n$個の爆弾がある。爆弾にはそれぞれ1から$n$までの番号が割り振られており、$i$番目の爆弾は座標$(x_i,y_i)$に存在している。
なお、どの爆弾も原点からのマンハッタン距離が等しいことが分かっている。
$i$番目の爆弾が爆発したとき、座標$(x_i,y_i)$からのマンハッタン距離が$r_i$以内の座標に存在している爆弾も連鎖的に爆発する。
$n$個の爆弾それぞれについて、その爆弾のみに着火した場合に、爆発せずに残る爆弾の個数を求めよ。

Input

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

入力はすべて整数で与えられる。
1行目に爆弾の個数$n$が与えられる。 続く$n$行のうち$i$行目には$i$番目の爆弾の情報を表す$x_i,y_i,r_i$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $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 )$
• 同じ座標に複数の爆弾が存在することはない

Output

$i$行目には$i$番目の爆弾のみに着火した場合に、爆発せずに残る爆弾の個数を出力せよ。

Sample Input 1

2
-1 -1 10
1 1 1

Sample Output 1

0
1

Sample Input 2

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

Sample Output 2

2
1
0

Note

Link

 

---