30772번 - Новогодний и прямоугольный 다국어인터랙티브

Это интерактивная задача.

На Новый год Дед Мороз подарил Глебу то, о чём он уже давно мечтал --- клетчатый квадрат размером $n \times n$. Подарок этот не простой, а с сюрпризом --- внутри квадрата Дед Мороз выбрал некоторый непустой прямоугольник, и в каждую клетку этого прямоугольника он положил по мандарину.

Теперь, чтобы получить желанный подарок, Глебу нужно сыграть с Дедом Морозом в очень интересную игру. Глеб должен отгадать, в каком именно прямоугольнике находятся все мандаринки, подаренные Дедом Морозом. Будем считать, что строки и столбцы занумерованы числами от $1$ до $n$ снизу вверх и слева направо. Глеб может производить два типа запросов:

• $?\,\,x_1\,y_1\,x_2\,y_2$ ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$) --- в ответ на этот запрос Дед Мороз говорит, сколько мандаринок находится в прямоугольнике, левым нижним углом которого является клетка $(x_1,\,y_1)$, а правым верхним --- клетка $(x_2,\,y_2)$;
• $!\,\,\,x_1\,y_1\,x_2\,y_2$ ($1 \le x_1 \le x_2 \le n$, $1 \le y_1 \le y_2 \le n$) --- когда Глеб уверен, что он точно знает, где находятся мандаринки, он должен сделать запрос такого вида, чтобы сообщить свой ответ. При этом $(x_1, y_1)$ соответствует предполагаемому расположению левого нижнего угла, а $(x_2, y_2)$ --- правого верхнего.

При запуске решения на вход вашей программе подается одно число $n$ ($1 \leq n \leq 2 \cdot 10^9$) --- размер квадрата.

Затем на каждый запрос типа "?" вам будет выдаваться количество мандаринок, находящихся в указанном вами прямоугольнике.

Вы должны выводить корректные запросы в формате, описанном выше. Последним должен следовать единственный запрос вида "!", после чего ваша программа должна немедленно завершиться. Ваша программа должна произвести не больше $q$ (параметр зависит от номера группы) запросов типа "?". Обратите внимание, что последний запрос, выводящий ответ, не входит в данные $q$ запросов.

В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасывайте буфер вывода --- для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.

Пример в условии иллюстрирует взаимодействие с проверяющей программой. Для прохождения первого теста не обязательно производить такие же запросы, как в примере.