Погризені книжки

Тисяча червів!______________

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

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

Усі N книг у бібліотеці зберігаються на одній дуже довгій полиці. Подивившись на корінець, Вася може визначити номер книги, не торкаючись її руками. Книги пронумеровані зліва праворуч, починаючи з одиниці. Жодна книга не перевернута зизу догори.

Вася виявив у бібліотеці M червів. Він визначив, де кожен черв'як почав і де завершив свій шлях. Усі черви рухались прямолінійно зліва праворуч або зправа ліворуч. Щоб вірно підрахувати збитки, Вася хоче написати програму, яка обчисляє, скільки сторінок погризли рівно k червів. Допоможіть йому це зробити.

Вхідні дані

У першому рядку вхідного файлу задано через пропуск два числа N і M (1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Другий рядок містить N додатніх цілих чисел p_i - кількість сторінок у i-й книзі (p_i ≤ 10000). У наступних M рядках містяться описи шляхів. Опис шляху складається з чотирьох додатніх цілих чисел - номер книги та номер сторінки початку шляху черв'яка, а також номер книги та номер сторінки завершення шляху черв'яка.

Вихідні дані

Вихідний файл повинен містити (M+1) рядок. У k-му рядку виведіть кількість сторінок, які погризли рівно (k-1) червів.