Погризені книжки#1760
Північний Європейський Університет славиться своєю бібліотекою. Проте, в акті заздрості, інший відомий університет запустив у НЕУ книжкових черв'яків. Тепер головний бібліотекар Олексій терміново має визначити масштаб пошкоджень.
Усі книг у бібліотеці стоять на одній, дуже довгій полиці. Дивлячись на корінці, Олексій може визначити номер кожної книги, не торкаючись її. Книги пронумеровані зліва направо, починаючи з першої. Жодна книга не стоїть догори дригом.
Олексій виявив у бібліотеці черв'яків. Він встановив, де кожен черв'як почав і закінчив свій шлях. Кожен черв'як рухався по прямій, або зліва направо, або справа наліво. Щоб правильно підрахувати шкоду, Олексій хоче написати програму, яка підрахує скільки сторінок було прогризено рівно черв'яками. Допоможіть йому у цьому.
У першому рядку вхідного файлу містяться два цілі числа і (1 \leq N \leq 10000, 1 \leq M \leq 100000), розділені пробілом. У другому рядку містяться додатних цілих чисел p_i, де p_i — кількість сторінок у -й книзі (p_i \leq 10000). Далі йдуть рядків, що описують шляхи черв'яків. Опис шляху містить чотири додатних цілих числа: номер книги та номер сторінки, де шлях починається, і номер книги та номер сторінки, де завершується.
У вихідний файл потрібно вивести (M+1) рядків. У -му рядку вивести кількість сторінок, які було прогризено рівно (k-1) черв'яками.
Приклад 1