Dwa prostokąty

To zadanie pochodzi z Codeforces. Tam też znajdują się testy do zadania.
Jeśli Twoje rozwiązanie zostanie pozytywnie ocenione na tamtych testach, należy wysłać tu zgłoszenie wypisujące "Zrobione".

Limit pamięci: 256MB

Na planszy n × n (n<=216 ) leżą dwa prostokąty o rozłącznych wnętrzach. Możesz zadawać do biblioteczki pytania o pewien prostokątny obszar planszy i w odpowiedzi otrzymywać liczbę prostokątów (0, 1 lub 2) znajdujących się w całości wewnątrz tego obszaru. Znajdź te prostokąty. Masz max 200 zapytań.

Wejście/Wyjście

Zadanie jest interaktywne. W pierwszym wierszu dana jest liczba n. Należy wypisywać zapytania postaci "? x1 y1 x2 y2".
Następnie na wejściu otrzymamy odpowiedź na zapytanie. Pod koniec należy wypisać wynik "! x11 y11 x12 y12 x21 y21 x22 y22".
Dokładniejsze informacje znajdują się na stronie codeforces.

Przykład

Wejście:
5
2
1
0
1
1
1
0
1

Wyjscie:
? 1 1 5 5
? 1 1 3 3
? 1 1 3 1
? 2 2 2 2
? 3 3 5 5
? 3 3 3 5
? 3 3 3 4
? 3 4 3 5
! 2 2 2 2 3 4 3 5