Kopalnia

Limit pamięci: 256 MB

Wszystkie bajtockie złoża diamentów występują na tej samej głębokości i mają postać prostokątów o bokach równoległych do osi pewnego układu współrzędnych. Złoża nie nachodzą na siebie, ale mogą stykać się bokami lub wierzchołkami.

Geologom nie udało się jeszcze wyjaśnić przyczyny tego fenomenu, ale opracowali dokładną mapę złóż. Wiąże się to z planami budowy nowej kopalni odkrywkowej. Obszar wyrobiska (również prostokątnego) będzie miał metrów długości i metrów szerokości. Rozważane są różne jego umiejscowienia. Dla każdego z możliwych położeń kopalni oblicz eksploatowaną przez nią powierzchnię złóż, czyli powierzchnię złóż położonych dokładnie pod wyrobiskiem kopalni.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite i () oznaczające liczbę złóż diamentów w Bajtocji oraz liczbę możliwych lokalizacji kopalni. W drugim wierszu znajdują się dwie liczby całkowite i () - długość i szerokość wyrobiska kopalni. Każdy z następnych wierszy zawiera po czwórce liczb całkowitych , , , . to współrzędne lewego dolnego, zaś - prawego górnego rogu -tego złoża. Złoża mają dodatnie pola. Wszystkie współrzędne należą do przedziału .

Dalej następuje wierszy zawierających po parze liczb całkowitych nieujemnych , (). Są to rozważane lokalizacje lewego dolnego rogu wyrobiska (wówczas prawy górny róg wyrobiska ma współrzędne ).

W testach wartych punktów zachodzi warunek .

Wyjście

Twój program powinien wypisać dokładnie wierszy, a w każdym z nich jedną liczbę całkowitą - pole powierzchni złóż diamentów pokrytych przez -te położenie wyrobiska.

Przykład

Dla danych wejściowych:

4 3
4 2
1 1 3 3
0 5 1 6
2 4 3 6
1 6 4 7
1 1
0 4
1 5

poprawną odpowiedzią jest:

4
3
4

Autor zadania: Bartosz Tarnawski.