Василий владеет квартирой в центре Лондона. Он решил сдавать квартиру в течение следующих $$$n$$$ дней, чтобы подзаработать денег.
Так как квартира Василия находится в центре города, то ему сразу пришло целых $$$m$$$ предложений вида $$$(l_i, r_i)$$$ обозначающего, что кто-то хочет забронировать квартиру со дня $$$l_i$$$ до дня $$$r_i$$$ включительно. Чтобы не тратить много времени на определение, выгодно ли ему соглашаться на предложение о съеме, Василий решил разработать алгоритм. Алгоритм обрабатывает все предложения в порядке их поступления и принимает очередное предложение $$$i$$$ в случае, если выполняются следующие два условия:
- $$$r_i - l_i + 1 \ge x$$$.
- Все дни на отрезке от $$$l_i$$$ до $$$r_i$$$ не заняты ни одним из ранее принятых предложений.
Василий не определился со значением, которому будет равен $$$x$$$, и просит у вас помощи. Он хочет, чтобы для всех $$$x$$$ от $$$1$$$ до $$$n$$$ вы посчитали суммарное количество дней, в которые будет сдаваться квартира, если алгоритм будет использовать соответствующий параметр $$$x$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ $$$(1 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5)$$$ — количество дней и количество предложений.
Следующие $$$m$$$ строк содержат по два целых числа $$$l_i$$$ и $$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ — описание $$$i$$$-го предложения на съем квартиры. Все предложения даны в хронологическом порядке.
Выведите $$$n$$$ целых чисел. Число в $$$i$$$-й строке должно обозначать количество дней, на которое будет сдана квартира, если алгоритм будет использовать $$$x$$$ равный $$$i$$$.
6 5 2 3 3 5 1 1 1 5 1 6
3 2 3 5 5 6
Описание отрезков из первого тестового примера для каждого $$$x$$$:
- $$$x = 1$$$ — алгоритм одобрит предложения: $$$1$$$ (2..3), $$$3$$$ (1..1). Суммарное количество дней, на которое Василий сдаст квартиру — 3
- $$$x = 2$$$ — алгоритм одобрит предложение $$$1$$$ (2..3). Суммарное количество дней, на которое Василий сдаст квартиру — 2
- $$$x = 3$$$ — алгоритм одобрит предложение $$$2$$$ (3..5). Суммарное количество дней, на которое Василий сдаст квартиру — 3
- $$$x = 4$$$ — алгоритм одобрит предложение $$$4$$$ (1..5). Суммарное количество дней, на которое Василий сдаст квартиру — 5
- $$$x = 5$$$ — алгоритм одобрит предложение $$$4$$$ (1..5). Суммарное количество дней, на которое Василий сдаст квартиру — 5
- $$$x = 6$$$ — алгоритм одобрит предложение $$$5$$$ (1..6). Суммарное количество дней, на которое Василий сдаст квартиру — 6
