Miny

Limit pamięci: 64 MB

Na prostej leżą miny przeciwpancerne. W razie wybuchu którejkolwiek z nich, wszystkie miny znajdujące się w jej promieniu rażenia również wybuchną. Określ, dla każdej z min, ile min wybuchnie, gdy tę jedną zdetonujemy "ręcznie".

Wejście

Pierwszy wiersz opisu zestawu zawiera liczbę min (). W kolejnych wierszach znajdują się po dwie liczby całkowite , (, ) - odpowiednio położenie i promień rażenia -tej miny. Miny podane są w kolejności rosnącego położenia . Żadne dwie miny nie leżą w jednym miejscu. Zasięg miny obejmuje również miny w odległości równej jej promieniowi rażenia.

Wyjście

Dla każdego zestawu danych wypisz (w pojedynczym wierszu) liczb całkowitych , gdzie oznacza liczbę min, które wybuchną przy zdetonowaniu -tej miny (wliczając samą -tą minę).

Przykład

Dla danych wejściowych:

1
5
0 2
2 1
3 2
4 1
6 2

poprawną odpowiedzią jest:

4 3 3 3 4

Zadanie zapożyczone z Chicago ACM.