eolymp
bolt
Try our new interface for solving problems
Məsələlər

Изгрызенные книги

Изгрызенные книги

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Тысяча червей!______________

из диалога преферансистов

Санкт-Петербургский Государственный Университет славится, в частности, своей библиотекой. Однако другой известный университет из зависти запустил в СПбГУ книжных червей. Теперь главному библиотекарю (его, кстати говоря, зовут Вася) нужно срочно определить величину ущерба.

Все N книг в библиотеке хранятся на одной очень длинной полке. Посмотрев на корешок, Вася может определить номер книги, не трогая её руками. Книги пронумерованы слева направо, начиная с единицы. Ни одна книга не перевёрнута вверх тормашками.

Вася обнаружил в библиотеке M червей. Он определил, где каждый червь начал и где закончил свой путь. Все черви двигались прямолинейно слева направо или справа налево. Чтобы правильно посчитать ущерб, Вася хочет написать программу, вычисляющую, сколько страниц изгрызло ровно k червей. Помогите ему это сделать.

Giriş verilənləri

В первой строке входного файла заданы через пробел два числа N и M (1N10000, 1M100000). Вторая строка содержит N положительных целых чисел p_i - количество страниц в i-й книге (p_i10000). В следующих M строках содержатся описания путей. Описание пути состоит из четырёх положительных целых чисел - номер книги и номер страницы начала пути червя, а также номер книги и номер страницы окончания пути червя.

Çıxış verilənləri

Выходной файл должен содержать (M+1) строк. В k-й строке выведите количество страниц, которые изгрызло ровно (k-1) червей.

Nümunə

Giriş verilənləri #1
3 2
1 1 1
1 1 3 1
2 1 2 1
Çıxış verilənləri #1
0
2
1