Стіл#9671

Стіл

1 секунда

128 мегабайтів

Дуже складна

Відомий шеф-кухар Клементина Дебоф купує нові столи для свого ресторану високого класу. Вона вирішила слідувати останньому тренду: великій моделі з численними, широкими, але водночас вишуканими орнаментами. Проте вона повинна бути впевнена, що ці декорації не заважають ідеально налаштованому розміщенню страв.

Прикраси зменшують площу столу, де офіціанти можуть безпечно ставити посуд. Клементина хоче, щоб усі страви можна було розмістити на столі на достатньо великій безпечній ділянці, тобто без накладання на будь-який орнамент. Знаючи розміри та розташування всіх декоративних областей, Клементина просить вас визначити, як ці прикраси впливають на доступні для страв місця.

Стіл має форму прямокутника з шириною $X$ і довжиною $Y$ міліметрів. На ньому розміщено $n$ орнаментів. Кожен орнамент розташований у фіксованих координатах столу і має форму прямокутника, сторони якого паралельні сторонам столу. Жодна з цих областей не перекриває іншу, але вони можуть торкатися одна одної.

У ресторані Клементини всі $d$ страв мають прямокутну форму і розташовуються так, щоб їхні сторони були паралельні сторонам столу в заздалегідь визначеній орієнтації. Офіціанти мають міліметрову точність: вони розміщують страви в цілих міліметрових координатах так, щоб їхні сторони були паралельні сторонам столу. Страви не повинні перекривати жодну декоративну область (але можуть торкатися її країв). З огляду на список страв, описаних їхніми розмірами, ваше завдання — для кожної з них визначити кількість цілих позицій, де цю страву можна безпечно розмістити на столі.

Примітка: на стіл подається лише одна страва; це означає, що вам не потрібно турбуватися про те, що страви можуть накладатися одна на одну, ви можете рахувати позиції для кожної страви незалежно.

Вхідні дані

Перший рядок містить цілі числа $X$ , $Y$ ( $1 \leq X, Y \leq 2000$ 1 \le X, Y \le 2000), $n$ ( $0 \leq n \leq 1 0^{6}$ 0 \le n \le 10^6) і $d$ ( $1 \leq d \leq 1 0^{5}$ 1 \le d \le 10^5).

Кожен з наступних $n$ рядків містить координати орнаменту — чотири цілі числа $x$ , $x^{'}$ x', $y$ і $y^{'}$ y', де $0 \leq x < x^{'} \leq X$ 0 \le x < x' \le X і $0 \leq y < y^{'} \leq Y$ 0 \le y < y' \le Y, описуючи орнамент між точками $(x, y)$ і $(x^{'}, y^{'})$ (x', y').

Кожен з наступних $d$ рядків містить ширину $x$ і довжину $y$ страви — два цілі числа, $0 < x \leq X$ 0 < x \le X і $0 < y \leq Y$ 0 < y \le Y.

Вихідні дані

Виведіть $d$ рядків, кожен з яких містить кількість можливих цілих позицій для відповідної страви.

Приклади

Приклад 1