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

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

Содержит один или несколько тестов. В первой строке каждого теста записано количество отрезков n (1 ≤ n ≤ 105). Следующие n строк описывают отрезки: i-я строка содержит пару целых чисел Li и Ri - координаты начала и конца i-го отрезка (-109 ≤ Li ≤ Ri ≤ 109). Общая сумма значений n во входных данных не превосходит 105. Входные данные завершаются нулём. Количество тестов не превосходит 104.

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

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