e-olymp
Задачі

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

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

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

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

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

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

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

Вхідні дані

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

Вихідні дані

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

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB
Вхідні дані
3 2
1 1 1
1 1 3 1
2 1 2 1
Вихідні дані
0
2
1