Изгрызенные книги
Тысяча червей!______________
из диалога преферансистов
Санкт-Петербургский Государственный Университет славится, в частности, своей библиотекой. Однако другой известный университет из зависти запустил в СПбГУ книжных червей. Теперь главному библиотекарю (его, кстати говоря, зовут Вася) нужно срочно определить величину ущерба.
Все N книг в библиотеке хранятся на одной очень длинной полке. Посмотрев на корешок, Вася может определить номер книги, не трогая её руками. Книги пронумерованы слева направо, начиная с единицы. Ни одна книга не перевёрнута вверх тормашками.
Вася обнаружил в библиотеке M червей. Он определил, где каждый червь начал и где закончил свой путь. Все черви двигались прямолинейно слева направо или справа налево. Чтобы правильно посчитать ущерб, Вася хочет написать программу, вычисляющую, сколько страниц изгрызло ровно k червей. Помогите ему это сделать.
Входные данные
В первой строке входного файла заданы через пробел два числа N и M (1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Вторая строка содержит N положительных целых чисел p_i - количество страниц в i-й книге (p_i ≤ 10000). В следующих M строках содержатся описания путей. Описание пути состоит из четырёх положительных целых чисел - номер книги и номер страницы начала пути червя, а также номер книги и номер страницы окончания пути червя.
Выходные данные
Выходной файл должен содержать (M+1) строк. В k-й строке выведите количество страниц, которые изгрызло ровно (k-1) червей.