D. Рекомендации
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, вы работаете в некоем стриминговом сервисе. В сервисе присутствуют $$$n$$$ активных пользователей и $$$10^9$$$ треков, которые эти пользователи могут прослушивать. Пользователи могут ставить лайки трекам, и на основе лайков сервис должен рекомендовать им новые треки.

Треки пронумерованы от $$$1$$$ до $$$10^9$$$. Оказалось, что треки, которые нравятся $$$i$$$-му пользователю, образуют отрезок $$$[l_i, r_i]$$$.

Скажем, что пользователь $$$j$$$ является предиктором для пользователя $$$i$$$ ($$$j \neq i$$$), если пользователь $$$j$$$ поставил лайки всем трекам, которые нравятся $$$i$$$-му пользователю (и, возможно, некоторым другим трекам тоже).

Также скажем, что трек сильно рекомендован для пользователя $$$i$$$, если трек еще не понравился $$$i$$$-му пользователю, но он понравился каждому предиктору $$$i$$$-го пользователя.

Посчитайте количество сильно рекомендованных треков для каждого пользователя $$$i$$$. Если у пользователя нет предикторов, то выведите $$$0$$$ для него.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют сами $$$t$$$ наборов.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество пользователей.

В следующих $$$n$$$ строках задано по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^9$$$) — отрезок треков, которые нравятся $$$i$$$-му пользователю.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, где $$$i$$$-е целое число — это количество сильно рекомендованных треков для $$$i$$$-го пользователя (или $$$0$$$, если у пользователя нет предикторов).

Пример
Входные данные
4
3
3 8
2 5
4 5
2
42 42
1 1000000000
3
42 42
1 1000000000
42 42
6
1 10
3 10
3 7
5 7
4 4
1 2
Выходные данные
0
0
1
999999999
0
0
0
0
0
2
3
2
4
8
Примечание

В первом наборе входных данных:

  • у первого пользователя нет предикторов;
  • у второго пользователя нет предикторов;
  • у третьего пользователя два предиктора: пользователи $$$1$$$ и $$$2$$$; только трек $$$3$$$ (из тех, которые еще не понравились третьему пользователю) понравился им обоим.

Во втором наборе входных данных второй пользователь является предиктором для первого пользователя. Поэтому все треки, кроме $$$42$$$-го, сильно рекомендованы для первого пользователя.

В третьем наборе входных данных у первого пользователя два предиктора: пользователи $$$2$$$ и $$$3$$$, но нет трека, который понравился бы им и не понравился бы самому пользователю.