\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}) червів.