\textit{Тысяча червей!______________} из диалога преферансистов \includegraphics{https://static.e-olymp.com/content/98/98491ff5741214ff643a9539384e7cc6815814c2.jpg} Санкт-Петербургский Государственный Университет славится, в частности, своей библиотекой. Однако другой известный университет из зависти запустил в СПбГУ книжных червей. Теперь главному библиотекарю (его, кстати говоря, зовут Вася) нужно срочно определить величину ущерба. Все \textbf{N} книг в библиотеке хранятся на одной очень длинной полке. Посмотрев на корешок, Вася может определить номер книги, не трогая её руками. Книги пронумерованы слева направо, начиная с единицы. Ни одна книга не перевёрнута вверх тормашками. Вася обнаружил в библиотеке \textbf{M} червей. Он определил, где каждый червь начал и где закончил свой путь. Все черви двигались прямолинейно слева направо или справа налево. Чтобы правильно посчитать ущерб, Вася хочет написать программу, вычисляющую, сколько страниц изгрызло ровно \textbf{k} червей. Помогите ему это сделать. \InputFile В первой строке входного файла заданы через пробел два числа \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}, \textbf{1} ≤ \textbf{M} ≤ \textbf{100000}). Вторая строка содержит \textbf{N} положительных целых чисел \textbf{p_i} - количество страниц в \textbf{i}-й книге (\textbf{p_i} ≤ \textbf{10000}). В следующих \textbf{M} строках содержатся описания путей. Описание пути состоит из четырёх положительных целых чисел - номер книги и номер страницы начала пути червя, а также номер книги и номер страницы окончания пути червя. \OutputFile Выходной файл должен содержать (\textbf{M+1}) строк. В \textbf{k}-й строке выведите количество страниц, которые изгрызло ровно (\textbf{k-1}) червей.