В Ужляндії знову щось трапилось! Усі жителі країни очікують гру між збірними командами Ужляндії та Овеанії з футболу.
Відомо, що футбольне поле – це матриця, що містить рядків та стовпців. Рядки матриці пронумеровані зверху вниз, стовпці – зліва направо. Команда Ужляндії складається з гравців. Кожен гравець характеризується ділянкою поля, у межах якої він гратиме. Також відомо, що така ділянка є прямокутником, сторони якого паралельні сторонам матриці.
Вважається, що два гравці зіграні, якщо перетин ділянок, у межах яких вони грають, непорожній. Іншими словами, два гравці зіграні, якщо існує елемент матриці, який належить обом прямокутникам, що характеризують цих гравців. Зіграністю команди вважається кількість пар гравців, що є зіграними.
Президент Ужляндії вирішив дізнатись зіграність збірної команди Ужляндії з футболу. Але, оскільки у нього багато справ, він доручив це завдання Вам.
У першому рядку вхідного файлу знаходиться два цілих числа та – кількість рядків та стовпців відповідно. У другому рядку знаходиться одне ціле число – кількість гравців у збірній команді Ужляндії з футболу.
У наступних рядках знаходиться по чотири цілих числа x_1, y_1, x_2, y_2 (1 \leqslant x_1 \leqslant x_2 \leqslant N;\ 1 \leqslant y_1 \leqslant y_2 \leqslant M), що описують ділянку у межах якої гратиме відповідний гравець у наступний спосіб: (x_1, y_1) – координата лівої верхньої клітинки прямокутника, а (x_2, y_2) – координата правої нижньої клітинки прямокутника.
Виведіть одне число – зіграність збірної команди Ужляндії з футболу.
Example 1
Ця задача складається з трьох підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі, а також всі тести всіх необхідних для неї підзадач. Необхідні підзадачі також вказані в таблиці.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 20 | 1 \leqslant Q \leqslant 1000 | |
2 | 30 | 1 \leqslant N \leqslant 7;\ 1 \leqslant M \leqslant 7 | |
3 | 50 | 1 \leqslant N \leqslant 1000;\ 1 \leqslant M \leqslant 1000;\ 1 \leqslant Q \leqslant 10^6 | Необхідні підзадачі: 0, 1, 2. |