eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Отрезки

Отрезки

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

Входные данные

Содержит один или несколько тестов. В первой строке каждого теста записано количество отрезков n (1n10^5). Следующие n строк описывают отрезки: i-я строка содержит пару целых чисел L[i] и R[i] - координаты начала и конца i-го отрезка (-10^9L[i]R[i]10^9). Общая сумма значений n во входных данных не превосходит 10^5. Входные данные завершаются нулём. Количество тестов не превосходит 10^4.

Выходные данные

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

prb5156.gif

Пример

Входные данные #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
Автор Иван Казменко, Олег Христенко