Plemiona [B]

Limit pamięci: 384 MB

UWAGA: Na prawdziwych zawodach limit pamięci wynosił 1024 MB.

Profesor Bajtowicz jest cieszącym się wielkim uznaniem historykiem. Ostatnio opracował śmiałą hipotezę, wyjaśniającą proces formowania się pierwszych państw na kontynencie Bajtopii. Powszechnie wiadomo, że zaraz po wielkiej wędrówce ludów tereny te zamieszkiwało plemion. Co ciekawe, każde z plemion zajmowało pewne terytorium, które na mapie Bajtopii jest prostokątem o bokach równoległych do boków mapy. Terytoria nie musiały być rozłączne, wobec tego na niektórych terenach dochodziło do spotkania kilku kultur.

W myśl hipotezy profesora Bajtowicza, jeżeli tylko przecięcie terytoriów dwóch plemion miało dodatnie pole, to po pewnym czasie te plemiona łączyły się. Dawało to bodziec do dalszej ekspansji i nowo powstałe plemię rozprzestrzeniało się wewnątrz najmniejszego prostokąta (o bokach równoległych do boków mapy) zawierającego oba ich dotychczasowe terytoria.

Profesor Bajtowicz twierdzi, że proces ten zachodził nieprzerwanie, aż w pewnym momencie przecięcie każdej pary terytoriów miało zerowe pole. Wtedy sytuacja ustabilizowała się i obszary zajmowane przez plemiona przekształciły się w pierwsze państwa.

Profesor wie, że nawet jego autorytet może nie wystarczyć, aby tak innowatorska hipoteza została przyjęta przez skostniałe środowisko naukowe. Na szczęście, dzięki swoim poprzednim badaniom, dysponuje on dwiema dokładnymi mapami. Jedna z nich opisuje lokalizacje pierwotnych plemion, zaś druga - pierwszych państw. Bajtowicz zatrudnił Cię potajemnie, abyś przeprowadził (na podstawie pierwszej mapy) symulację rozwoju plemion według jego modelu. Kiedy dostarczysz mu teoretyczne wyniki, porówna je z faktycznym rozmieszczeniem państw na drugiej mapie i stwierdzi, czy jego hipoteza ma szanse być prawdziwa.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę pierwotnych plemion zamieszkujących Bajtopię. Następne wierszy zawiera po cztery liczby całkowite , , oraz , , oznaczające, że pewne plemię zamieszkiwało terytorium, które na mapie jest prostokątem, którego dwa przeciwległe wierzchołki to oraz .

Wyjście

Twój program powinien wypisać w pierwszym wierszu jedną liczbę całkowitą , oznaczającą liczbę państw, które powinny powstać według hipotezy Bajtowicza. Następnie Twój program powinien wypisać wierszy, a w każdym z nich cztery liczby całkowite , , i pooddzielane pojedynczymi odstępami, oznaczające, że terytorium jednego z państw jest na mapie prostokątem o przeciwległych wierzchołkach oraz , przy czym , . Czwórki te muszą być różne oraz powinny zostać wypisane w kolejności leksykograficznej.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

2
1 6 2 9
7 8 1 4

Autor zadania: Bartosz Tarnawski.