Masa
Məşhur aşpaz Klementina Debof öz 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, bu dekorasiyaların mükəmməl yemək balansını pozmadığından ə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əşdirilsin, 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 izah 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ə onların tərəfləri masanın tərəflərinə paralel şəkildə əvvəlcədən müəyyən edilmiş istiqamətdə yerləşdirilir. Ofisiantlar millimetrlik dəqiqliyə malikdirlər: onlar yeməkləri masanın tərəflərinə paralel olacaq şəkildə 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ə təsvir olunan siyahını nəzərə alaraq, sizin vəzifəniz hər biri üçün masada təhlükəsiz yerləşdirilə biləcək (tam) yerlərin sayını göstərməkdir. Qeyd: masaya yalnız bir yemək təqdim olunur; bu o deməkdir ki, yeməklərin bir-birini örtməsi barədə 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 ≤ X, Y ≤ 2000), n (0 ≤ n ≤ 10^6) və d (1 ≤ d ≤ 10^5) ehtiva edir. Növbəti n sətir hər bir naxışın koordinatlarını ehtiva edir - dörd tam ədəd x, x', y və y', burada 0 ≤ x < x' ≤ X və 0 ≤ y < y' ≤ Y, naxışı (x, y) və (x', y') nöqtələri arasında təsvir edir. Növbəti d sətir yeməklərin eni x və uzunluğu y - iki tam ədəd, 0 < x ≤ X və 0 < y ≤ Y ehtiva edir.
Çıxış Məlumatları
Hər yemək üçün mümkün yerləşdirmələrin sayını ehtiva edən d sətir çıxarın.