F. Волонтёрство
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Артём организует Чемпионат Кыргызстана по программированию.

Соревнование пройдёт во временном промежутке [S;F].

Для помощи в организации соревнования Артём набрал n волонтёров. Известно, что i-й волонтёр сможет помочь во временном промежутке [bi, ei].

Артём понимает, что может случиться всякое, поэтому для каждого момента t времени он ввёл «индекс помощи» H(t) — количество волонтёров, которые в момент времени t могут помочь ему решить ту или иную проблему.

Формально говоря, индекс помощи H(t) равен количеству волонтёров таких, что bi ≤ t ≤ ei.

Артём продумывает различные сценарии развития событий, поэтому для каждого значения h [1... n] он хочет знать, какое суммарное время в течение чемпионата индекс помощи H(t) будет строго меньше h.

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

В первой строке содержится целое число n (1 ≤ n ≤ 3·105) — количество волонтёров.

Во второй строке содержатся целые числа S и F (1 ≤ S < F ≤ 109) — начало и конец временного промежутка чемпионата.

В каждой из следующих n строк содержится по два целых числа bi и ei (1 ≤ bi < ei ≤ 109) — начало и конец временного отрезка, когда доступен i-й волонтёр.

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

Выведите n чисел t1, t2, ..., tn, где th — суммарное время в течение чемпионата, когда «индекс помощи» строго меньше h.

Пример
Входные данные
5
10 20
5 12
16 19
15 25
8 14
13 17
Выходные данные
0 3 9 10 10
Примечание

Первый тестовый пример

  • Индекс помощи никогда не будет 0 в течение чемпионата, откуда t1 = 0.
  • Индекс помощи 1 будет в промежутках [12;13], [14;15] и [19;20] — суммарная длительность промежутков равна 3, откуда t2 = 3 + 0 = 3.
  • Индекс помощи 2 будет в промежутках [10;12], [13;14], [15;16] и [17;19] — суммарная длительность равна 6, откуда t3 = 6 + 3 + 0 = 9.
  • Индекс помощи 3 будет в промежутке [16;17] — суммарная длительность равна 1, откуда t4 = 1 + 6 + 3 + 0 = 10.
  • Индекс помощи никогда не будет равен 4, поэтому t5 = 10 аналогично t4.