Стіл
Відомий шеф-кухар Клементина Дебоф купує нові столи для свого ресторану високого класу. Вона вирішила слідувати останньому тренду — великій моделі з численними широкими, але водночас вишуканими орнаментами. Проте, вона повинна бути впевнена, що ці декорації не завадять ідеально налаштованому розміщенню страв.
Прикраси зменшують площу столу, де офіціанти можуть безпечно ставити посуд. Клементина хоче, щоб усі страви можна було розмістити на столі на достатньо великій безпечній ділянці, тобто без накладання на будь-які прикраси. Знаючи розміри та розташування всіх декоративних областей, Клементина просить вас визначити, як ці прикраси впливають на доступні місця для посуду.
Стіл має форму прямокутника з шириною X і довжиною Y міліметрів. На ньому розміщено n орнаментів. Кожен орнамент розташований у фіксованих координатах столу і має форму прямокутника, сторони якого паралельні сторонам столу. Жодна з цих областей не перекриває іншу, але вони можуть торкатися одна одної.
У ресторані Клементини всі d страви мають прямокутну форму і розташовуються так, щоб їхні сторони були паралельні сторонам столу в заздалегідь визначеній орієнтації. Офіціанти мають міліметрову точність: вони розміщують страви в цілочисельних міліметрових координатах так, щоб їхні сторони були паралельні сторонам столу. Страви не повинні перекривати жодну декоративну область (але можуть торкатися її країв). З огляду на список страв, описаних їхніми розмірами, ваше завдання полягає в тому, щоб вказати для кожної з них кількість (цілих) місць, де її можна безпечно розмістити на столі. Примітка: на стіл подається лише одна страва; це означає, що вам не потрібно турбуватися про те, що страви можуть перекриватися, ви можете розраховувати місця для кожної страви незалежно від інших.
Вхідні дані
Перший рядок містить цілі числа X, Y (1 ≤ X, Y ≤ 2000), n (0 ≤ n ≤ 10^6) і d (1 ≤ d ≤ 10^5). Кожен з наступних n рядків містить координати орнаменту — чотири цілі числа x, x', y і y', де 0 ≤ x < x' ≤ X і 0 ≤ y < y' ≤ Y, описуючи орнамент між точками (x, y) і (x', y'). Наступні d рядків містять ширину x і довжину y страв — два цілі числа, 0 < x ≤ X і 0 < y ≤ Y.
Вихідні дані
Виведіть d рядків, кожен з яких містить кількість можливих розташувань для відповідної страви.