Банка з черв'яками
Є старе прислів'я про відкриття банки з черв'яками. Менш відоме прислів'я про стрілянину по банці з вибуховими черв'яками з пневматичної гвинтівки.
Уявімо, що ми розміщуємо кілька банок з вибуховими черв'яками на довгому, прямому паркані. Коли в банку стріляють, усі черв'яки всередині вибухають. Різні види черв'яків мають різні радіуси вибуху. Кожна банка містить лише один вид черв'яків.
Коли банка вибухає, якщо інша банка знаходиться в радіусі вибуху, то вона також вибухне, можливо, створюючи ланцюгову реакцію. Кожна банка вибухає лише один раз. Цей процес триває, поки всі вибухи не припиняться.
Для кожної банки, припустимо, що вона єдина, в яку стріляють. Скільки банок загалом вибухне?
Вхідні дані
У вхідних даних буде кілька тестових випадків. Кожен тестовий випадок починається з рядка з одним цілим числом n (1 ≤ n ≤ 100000), що представляє кількість банок на цьому паркані. Кожен з наступних n рядків міститиме два цілі числа x (-10^9 ≤ x ≤ 10^9) та r (1 ≤ r ≤ 10^9), де x — це місце розташування банки на паркані, а r — радіус вибуху. Жодні дві банки не займатимуть одне й те саме місце. Вхідні дані завершуються рядком з одним числом 0.
Вихідні дані
Для кожного паркану виведіть n цілих чисел в одному рядку, розділених одним пробілом. i-те число представляє кількість банок, які вибухнуть, якщо вистрілити в i-ту банку. Не виводьте зайвих пробілів і не друкуйте порожніх рядків між вихідними даними.