e-olymp
Змагання

July 9 - ADA Training

Відрізки

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

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

prb5156.gif

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 2
2 3
3 4
4
1 6
2 3
4 5
7 8
0
Вихідні дані #1
Case 1: 1 2 1
Case 2: 2 1 1 0
Автор Іван Казменко, Олег Христенко