Задано $$$n$$$ отрезков на координатной прямой; концы отрезков имеют целочисленные координаты. Отрезки могут вырождаться в точки. Отрезки могут пересекаться друг с другом, вкладываться и даже совпадать.
Ваша задача: для каждого $$$k \in [1..n]$$$ посчитать количество таких точек с целочисленными координатами, что количество отрезков, покрывающих эти точки, равно $$$k$$$. Отрезок с границами $$$l_i$$$ и $$$r_i$$$ покрывает точку $$$x$$$ тогда и только тогда, когда $$$l_i \le x \le r_i$$$.
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество отрезков.
Следующие $$$n$$$ cтрок содержат отрезки. Строка с индексом $$$i$$$ состоит из пары целых чисел $$$l_i, r_i$$$ ($$$0 \le l_i \le r_i \le 10^{18}$$$) — концы $$$i$$$-го отрезка.
Выведите $$$n$$$ целых чисел через пробел $$$cnt_1, cnt_2, \dots, cnt_n$$$, где $$$cnt_i$$$ равно количеству таких точек, что количество отрезков, покрывающих эти точки, равно $$$i$$$.
3
0 3
1 3
3 8
6 2 1
3
1 3
2 4
5 7
5 2 0
Картинка, описывающая первый тестовый пример:
Точки с координатами $$$[0, 4, 5, 6, 7, 8]$$$ покрыты одним отрезком, точки $$$[1, 2]$$$ покрыты двумя отрезками и точка $$$[3]$$$ покрыта тремя отрезками.
Картинка, описывающая второй тестовый пример:
Точки $$$[1, 4, 5, 6, 7]$$$ покрыты одним отрезком, точки $$$[2, 3]$$$ покрыты двумя отрезками и точек, покрытых тремя отрезками, нет.
