8654번 - Działka 다국어

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 k × k i rośnie w nim n 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.

Pierwszy wiersz wejścia zawiera dwie liczby całkowite k oraz n (1 ≤ k ≤ 1 000 000, 3 ≤ n ≤ 3 000), oznaczające długość boku fragmentu puszczy i liczbę sosen rosnących w tym fragmencie. Każdy z kolejnych n wierszy zawiera dwie liczby całkowite x_i, y_i (0 ≤ x_i, y_i ≤ k), oznaczające współrzędne punktu, w którym znajduje się i-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ą m (1 ≤ m ≤ 1 000 000), oznaczającą liczbę możliwych lokalizacji działki. Każdy z kolejnych m wierszy zawiera cztery liczby całkowite a_j, b_j, c_j, d_j (0 ≤ a_j < b_j ≤ k, 0 ≤ c_j < d_j ≤ k), opisujące prostokątną działkę [a_j,b_j] × [c_j,d_j].

Twój program powinien wypisać na wyjście m wierszy; j-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 j-tej oferty. Możesz założyć, że pole to będzie zawsze dodatnie.

Rysunek przedstawia pierwsze dwie oferty lokalizacji działki z zaznaczeniem ogrodzonego obszaru.