Ніякі дві букви не повинні мати спільної крапки. А також спільного тире

Інструкція для телеграфістів

Директор Інституту Геометрії Відрізків (ІГО) прийняв Ааза у своєму кабінеті. Судячи по обстановці, інститут не бідував. Проблема на цей раз була в іншому.

Мы не стоїмо без роботи. Кожного разу, після початку сезону у чемпіонатах з програмування, ми розв'язуємо безліч задач на перетин двох відрізків по замовленню організаторів змагань. Але це усе-таки рутина, і співробітники починають втрачати інтерес. У деяких місцях навіть замість роботи займаються самодіяльністью - влаштовують концерти для баяна при свічках. Чи можете сформулювати для нас задачу, відмінну від цієї, але яке не дуже відрізняється від неї за формулюванням.

Ну наприклад... Задано n відрізків на прямій. Для кожного відрізка порібно обчислити кількість відрізків, які мають з ним хоча б одну спільну точку.

Співробітники ІГО з ентузіазмом взялись за задачу. Більше того - вони доручили Вам написати програму для її розв'язання.

Вхідні дані

Містить один або декілька тестів. У першому рядку кожного тесту записано кількість відрізків n (1 ≤ n ≤ 105). Наступні n рядків описують відрізки; i-ий рядок містить пару цілих чисел Li та Ri - координати початку та кінця i-го відрізка (-109 ≤ Li ≤ Ri ≤ 109). Загальна сума значень n по вхідним даним не перевищує 105. Вхідні дані завершуються нулем. Кількість тестів не перевищує 104.

Вихідні дані

Для кожного тесту виведіть в одному рядку n чисел, як показано у прикладі: i-те число - кількість відрізків, з якими i-ий відрізок має хоча б одну спільну точку, не рахуючи його самого. Дотримуйтесь формату виведення максимально точно.