Предположим, вы работаете в некоем стриминговом сервисе. В сервисе присутствуют \(n\) активных пользователей и \(10^9\) треков, которые эти пользователи могут прослушивать. Пользователи могут ставить лайки трекам, и на основе лайков сервис должен рекомендовать им новые треки.
Треки пронумерованы от \(1\) до \(10^9\). Оказалось, что треки, которые нравятся \(i\)-му пользователю, образуют отрезок \([l_i, r_i]\).
Скажем, что пользователь \(j\) является предиктором для пользователя \(i\) (\(j \neq i\)), если пользователь \(j\) поставил лайки всем трекам, которые нравятся \(i\)-му пользователю (и, возможно, некоторым другим трекам тоже).
Также скажем, что трек сильно рекомендован для пользователя \(i\), если трек еще не понравился \(i\)-му пользователю, но он понравился каждому предиктору \(i\)-го пользователя.
Посчитайте количество сильно рекомендованных треков для каждого пользователя \(i\). Если у пользователя нет предикторов, то выведите \(0\) для него.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел, где \(i\)-е целое число — это количество сильно рекомендованных треков для \(i\)-го пользователя (или \(0\), если у пользователя нет предикторов).
Примечание
В первом наборе входных данных:
- у первого пользователя нет предикторов;
- у второго пользователя нет предикторов;
- у третьего пользователя два предиктора: пользователи \(1\) и \(2\); только трек \(3\) (из тех, которые еще не понравились третьему пользователю) понравился им обоим.
Во втором наборе входных данных второй пользователь является предиктором для первого пользователя. Поэтому все треки, кроме \(42\)-го, сильно рекомендованы для первого пользователя.
В третьем наборе входных данных у первого пользователя два предиктора: пользователи \(2\) и \(3\), но нет трека, который понравился бы им и не понравился бы самому пользователю.