Василий владеет квартирой в центре Лондона. Он решил сдавать квартиру в течение следующих \(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\) целых чисел. Число в \(i\)-й строке должно обозначать количество дней, на которое будет сдана квартира, если алгоритм будет использовать \(x\) равный \(i\).
Примечание
Описание отрезков из первого тестового примера для каждого \(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
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 5
2 3
3 5
1 1
1 5
1 6
|
3
2
3
5
5
6
|