Masa#9671

Masa

1 saniyə

128 meqabayt

Çox çətin

Məşhur aşpaz Klementina Debof yüksək səviyyəli restoranı üçün yeni masalar alır. O, son trendlərə uyğun olaraq, geniş və zərif naxışlarla bəzədilmiş böyük modellərə üstünlük verir. Lakin o, bu dekorasiyaların mükəmməl yemək düzümünə mane olmamasına əmin olmaq istəyir.

Bəzəklər masanın düz səthini azaldır - burada ofisiantlar qab-qacağı təhlükəsiz şəkildə yerləşdirə bilərlər. Klementina istəyir ki, bütün yeməklər masanın üzərində kifayət qədər böyük təhlükəsiz sahədə yerləşdirilə bilsin, yəni heç bir bəzək üst-üstə düşməsin. Bütün dekorativ sahələrin ölçülərini və yerləşməsini bilən Klementina sizdən bu bəzəklərin qab-qacaq üçün əlçatan yerlərə necə təsir etdiyini müəyyən etməyinizi xahiş edir.

Masa eni $X$ və uzunluğu $Y$ millimetr olan düzbucaqlıdır. Onun üzərində $n$ naxış yerləşdirilib. Hər biri masanın sabit koordinatlarında yerləşir və tərəfləri masanın tərəflərinə paralel olan düzbucaqlı formadadır. Bu sahələrin heç biri bir-birini örtmür, lakin onlar bir-birinə toxuna bilərlər.

Klementinanın restoranında bütün $d$ yeməklər düzbucaqlı formadadır və qabaqcadan müəyyən edilmiş istiqamətdə, tərəfləri masanın tərəflərinə paralel şəkildə yerləşdirilir. Ofisiantlar millimetrlik dəqiqliyə malikdirlər: onlar yeməkləri masanın tərəflərinə paralel olmaqla, tam millimetrlik koordinatlarda yerləşdirəcəklər. Yeməklər heç bir dekorativ sahəni örtməməlidir (lakin onların kənarlarına toxuna bilər). Yeməklərin ölçüləri ilə göstərilən siyahını nəzərə alaraq, sizin vəzifəniz — hər biri üçün masada təhlükəsiz yerləşə biləcək (tam) yerlərin sayını tapmaqdır.

Qeyd: masaya yalnız bir yemək verilir; bu o deməkdir ki, yeməklərin bir-birini örtəcəyindən narahat olmağa ehtiyac yoxdur, hər yemək üçün yerləri digərindən asılı olmayaraq hesablaya bilərsiniz.

Giriş Məlumatları

Birinci sətir tam ədədləri $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) və $d$ ( $1 \leq d \leq 1 0^{5}$ 1 \le d \le 10^5) ehtiva edir.

Növbəti $n$ sətirin hər biri naxışın koordinatlarını ehtiva edir — dörd tam ədəd $x$ , $x^{'}$ x', $y$ və $y^{'}$ y', burada $0 \leq x < x^{'} \leq X$ 0 \le x < x' \le X və $0 \leq y < y^{'} \leq Y$ 0 \le y < y' \le Y, naxışı $(x, y)$ və $(x^{'}, y^{'})$ (x', y') nöqtələri arasındakı sahədə təsvir edir.

Növbəti $d$ sətirdə yeməklərin eni $x$ və uzunluğu $y$ — iki tam ədəd, $0 < x \leq X$ 0 < x \le X və $0 < y \leq Y$ 0 < y \le Y verilir.

Çıxış Məlumatları

Hər yemək üçün mümkün yerləşmələrin sayını göstərən $d$ sətir çıxarın.

Nümunələr

Nümunə 1