Działka [B]

Limit pamięci: 256 MB

Bajtazar od dziecka marzył o działce w Puszczy Bajtockiej. Obecnie pracuje jako informatyk i wreszcie może sobie pozwolić na realizację tego marzenia.

Spółka Lasy Bajtockie właśnie rozpoczęła sprzedaż działek w nowym fragmencie puszczy, a Bajtazar zgłosił się jako pierwszy klient. Ów fragment puszczy z lotu ptaka wygląda jak kwadrat o wymiarach i rośnie w nim sosen. Jako pierwszy klient Bajtazar ma do wyboru wiele ofert lokalizacji działki. Każda z ofert ma postać prostokąta położonego w całości we fragmencie puszczy. Bajtazar nie wie jeszcze, którą ofertę wybrać.

Po zakupie działki Bajtazar zamierza ogrodzić ją płotem. Bajtazar jest oszczędny i chciałby, żeby płot był jak najkrótszy, a zarazem ogradzał wszystkie drzewa rosnące na terenie działki. To, w szczególności, oznacza, że nie cały teren prostokątnej działki musi zostać ogrodzony. Bajtazar wie również, że każdego roku będzie musiał odprowadzić podatek gruntowy, którego wysokość będzie proporcjonalna do powierzchni ogrodzonego obszaru działki. I to głównie ten niemały podatek martwi Bajtazara.

Pomóż Bajtazarowi w podjęciu decyzji i oblicz, dla każdej zaproponowanej przez Lasy Bajtockie lokalizacji działki, jak duża byłaby powierzchnia ogrodzonego obszaru działki.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz (, ), oznaczające długość boku fragmentu puszczy i liczbę sosen rosnących w tym fragmencie. Każdy z kolejnych wierszy zawiera dwie liczby całkowite , (), oznaczające współrzędne punktu, w którym znajduje się -ta sosna. Możesz założyć, że w każdym punkcie znajduje się co najwyżej jedna sosna.

Kolejny wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę możliwych lokalizacji działki. Każdy z kolejnych wierszy zawiera cztery liczby całkowite , , , (, ), opisujące prostokątną działkę .

Wyjście

Twój program powinien wypisać na wyjście wierszy; -ty z tych wierszy powinien zawierać jedną liczbę rzeczywistą, podaną z dokładnością do jednej cyfry po kropce dziesiętnej: pole ogrodzonego obszaru działki przy wyborze -tej oferty. Możesz założyć, że pole to będzie zawsze dodatnie.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

4.0
10.0
6.0

Wyjaśnienie do przykładu: Rysunek przedstawia pierwsze dwie oferty lokalizacji działki z zaznaczeniem ogrodzonego obszaru.

Autor zadania: Adam Karczmarz.