有一句关于“打开潘多拉魔盒”（can of worms）的古老谚语。还有一句鲜为人知的谚语，是关于用气枪射击装有爆炸蠕虫的罐子的。

想象一下，我们在一条笔直的长栅栏上放置了一些装有爆炸蠕虫的罐子。当一个罐子被射中时，里面的所有蠕虫都会爆炸。不同种类的蠕虫有不同的爆炸半径。每个罐子只包含一种蠕虫。

当一个罐子爆炸时，如果另一个罐子处于其爆炸半径内，那么那个罐子也会爆炸，并可能引发连锁反应。每个罐子只会爆炸一次。这个过程会一直持续，直到所有爆炸停止。

对于每个罐子，假设它是唯一被射中的罐子。总共会有多少个罐子爆炸？

输入格式

输入包含多个测试用例。每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 100,000$)，表示栅栏上的罐子数量。接下来的 $n$ 行，每行包含两个整数 $x$ ($-10^9 \le x \le 10^9$) 和 $r$ ($1 \le r \le 10^9$)，其中 $x$ 是罐子在栅栏上的位置，$r$ 是爆炸半径。没有两个罐子会占据相同的位置。输入以一行包含单个 $0$ 的数据结束。

输出格式

对于每个栅栏，在一行中打印 $n$ 个整数，并用空格分隔。第 $i$ 个整数表示如果射中第 $i$ 个罐子，总共会爆炸的罐子数量。不要输出多余的空格，也不要在不同测试用例的输出之间打印任何空行。

样例

样例输入 1

3
4 3
-10 9
-2 3
12
2 2
7 7
10 1
19 3
23 12
29 8
33 1
35 17
39 2
40 1
46 11
52 3
0

样例输出 1

1 2 1
1 3 1 1 9 9 1 9 2 2 9 1