Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Многословие

(Время: 5 сек. Память: 16 Мб Сложность: 68%)

Поликарп приехал в столицу Байтландии, чтобы как следует осмотреть Байтландский Музей. В музее все экспонаты выстроены в ряд и пронумерованы от 1 до N. Он решил провести в столице Q дней. Каждый день он планирует посещать музей, просматривая отрезок экспонатов, начиная с экспоната Lk и заканчивая экспонатом Rk.

Просматривая экспонаты, Поликарп записывает свои впечатления в блокнот. Так как просмотр начинается с утра, то вначале Поликарп не многословен и записывает всего одни эпитет про первый просмотренный экспонат. Далее Поликарп чувствует прилив эмоций и записывает всё больше слов об очередном экспонате. Формально, на i-ом просмотренном экспонате Поликарп записывает i2 эпитетов в описание этого экспоната в свой блокнот.

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

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

В первой строке входного файла OUTPUT.TXT содержатся два целых числа N и Q (1 ≤ N, Q ≤ 500 000). В следующих Q строках следуют параметры отрезков в виде пары чисел Lk и Rk (1 ≤ Lk, Rk ≤ N, 1 ≤ k ≤ Q).

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

В выходной файл OUTPUT.TXT выведите N строк, в i-ой из которых должно содержаться количество эпитетов, записанных для i-го экспоната.

Пример

INPUT.TXTOUTPUT.TXT
16 3
1 3
6 3
5 6
1
4
25
9
5
5

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

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 A. Простой шифр
 B. Лягушка
 C. Электронная очередь
 D. Производная
 E. Степени двойки
 F. Сыграем?
 G. Вася и отрезки
 H. Различные префиксы
 I. Взрывчатка
 J. Перестановка
 K. Многословие
 L. Подготовка к ЕГЭ

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru