I. Падающие блоки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп изобрел новую мобильную игру с падающими блоками.

В этой игре $$$n$$$ блоков падают, по-одному за раз, на плоскую поверхность шириной $$$d$$$ единиц. Каждый блок можно представить как прямоугольник с координатами от $$$l_i$$$ до $$$r_i$$$ и единичной шириной, падающий вниз с большой высоты. Блок падает, пока не столкнется с плоской поверхностью или другим блоком. Будем говорить, что блок $$$a$$$ накрывает блок $$$b$$$, если $$$l_a \le l_b \le r_b \le r_a$$$.

Рассмотрим, что происходит, когда падает блок $$$i$$$. Если этот (верхний) блок $$$i$$$ сталкивается с любым блоком $$$j$$$, таким что блок $$$i$$$ не накрывает блок $$$j$$$, то блок $$$i$$$ упрется в блок $$$j$$$, и все блоки останутся на месте. В противном случае, все блоки, с которыми блок $$$i$$$ столкнулся и накрывает будут уничтожены, а блок $$$i$$$ продолжит падать, не теряя способности уничтожать другие блоки.

Например, рассмотрим, что случится, когда будут падать блоки $$$(1,2)$$$, $$$(2,3)$$$ и $$$(1,3)$$$ в данном порядке. Первый блок приземлится на плоскую поверхность. Далее, второй блок упрется в первый блок. Наконец, третий блок сначала уничтожит второй блок, продолжит падать, уничтожит первый блок и приземлится на плоскую поверхность.

Выше изображен пример из условия, он же является первым примером.

Помогите Поликарпу определить количество оставшихся блоков после падения каждого из них!

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

В первой строке заданы два целых числа $$$n$$$ и $$$d$$$ ($$$1 \le n, d \le 10^5$$$) — количество падающих блоков и длина плоской поверхности.

В $$$i$$$-й из следующих $$$n$$$ строк заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le d$$$), описывающих координаты $$$i$$$-го блока.

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

Выведите $$$n$$$ чисел, где $$$i$$$-е число равно количеству оставшихся блоков после падения $$$i$$$-го из них.

Примеры
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
1
2
1
Входные данные
8 6
1 2
3 3
2 3
1 3
2 4
3 6
1 5
1 5
Выходные данные
1
2
3
1
2
3
4
4
Примечание

Первый пример соответствует примеру из условия.

Во втором примере, происходят следующие изменения:

  • Блок $$$1$$$ приземлится на плоскую поверхность.
  • Блок $$$2$$$ приземлится на плоскую поверхность.
  • Блок $$$3$$$ приземлится на блоки $$$1$$$ и $$$2$$$. Заметим, что блок $$$3$$$ не уничтожит блок $$$2$$$, потому что не покрывает блок $$$1$$$ и упирается в него.
  • Блок $$$4$$$ уничтожит все блоки и приземлится на плоскую поверхность.
  • Блок $$$5$$$ приземлится на блок $$$4$$$.
  • Блок $$$6$$$ приземлится на блок $$$5$$$.
  • Блок $$$7$$$ приземлится на блок $$$6$$$. Заметим, что никакие блоки не будут уничтожены, потому что, хотя блок $$$7$$$ покрывает блоки $$$4$$$ и $$$5$$$, но он их не касается.
  • Блок $$$8$$$ уничтожит блок $$$7$$$ и приземлится на $$$6$$$.