HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Евгений и Пикабу

Section problems

• Довольно грустная задача
• Довольно грустная задача (услож...
• Долина бандитов
• Долина бандитов
• Домино
• Древний шифр
• ЕГЭ — B1
• ЕГЭ — B1
• Евгений и Пикабу
• Евгений и задачи
• Евклидов граф
• Ежевика
• Ежевика
• Жадина
• Жадина
• Забор
• Забор

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

Евгений и Пикабу
Евгений и Пикабу
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Если вы вдруг не знаете, Пикабу — это такой популярный сайт со смешными картинками и невероятными историями, успешно и массово убивающий время сотен тысяч людей. Евгений довольно давно не заходил на Пикабу — и, наконец, сорвался.

За время отсутствия Евгения на сайте накопилось N новых постов (мини-статей). Для удобства пронумеруем их от 1 до N.

Несмотря на впечатляющую усидчивость Евгения, даже ему могло оказаться не под силу прочитать все посты за один присест. Поэтому Евгений заходил на сайт M раз, в течение i-го из которых он читал посты с номерами от Li до Ri (возможно, некоторые из них он уже видел ранее — но разве Евгения это остановит?).

В какой-то момент Евгению стало интересно, какое общее количество различных постов он прочитал. Помогите ему ответить на этот вопрос.

А чтобы задача не показалась вам слишком простой, выводите ответ после каждого из M визитов Евгения на сайт.

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

Первая строка содержит целые числа N и M (1 ≤ N ≤ 1012, 1 ≤ M ≤ 105) — соответственно количество постов на сайте и количество визитов Евгения.

Следующие M строк описывают визиты Евгения. Каждая из них содержит целые числа Li и Ri (1 ≤ Li ≤ Ri ≤ N) — номера первого и последнего из постов, просмотренных Евгением в течение визита.

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

Выведите M целых чисел — общие количества различных постов, просмотренных Евгением после каждого захода на сайт.

Примеры

Входные данные
10 5
1 3
6 9
3 4
8 9
5 8
Выходные данные
3 7 8 8 9 
Входные данные
20 6
5 10
12 20
1 3
4 8
11 11
2 19
Выходные данные
6 15 18 19 20 20 

Для отправки решений необходимо выполнить вход.

www.contester.ru