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

Первое, что должен сделать преподаватель олимпиадного программирования, — это лечить новобранца от серьезной, но вполне излечимой болезни — питонизма.

Марат В. — специалист по лечению данной болезни, но, к сожалению, марганцовка закончилась. Тогда у преподавателей не осталось выбора, кроме как спрятать знания Андрея по злосчастному языку программирования в очень надёжном месте: заначке в паркете аудитории $$$113$$$.

Паркет в аудитории $$$113$$$ представляет собой квадрат со стороной $$$n - 1$$$ на координатной плоскости и содержит $$$n^2$$$ точек с натуральными координатами, а заначка — точка на этой плоскости внутри или на стороне квадрата. Андрей первый год ходит на программирование, поэтому он не знает, где она находится. Единственное, что может делать Андрей — задавать глупые вопросы своему соседу Цукерману. Вопросы бывают трёх видов:

1) Андрей может спросить про конкретную точку, является ли она заначкой;

2) Андрей может спросить про отрезок, заданный координатами его концов, при этом его концы не совпадают — лежит ли загаданная точка на этом отрезке;

3) Андрей может спросить про треугольник, заданный координатами его вершин, при этом треугольник невырожденный — лежит ли загаданная точка внутри или на границе этого треугольника.

В любом запросе координаты точек должны быть натуральными числами.

Цукерман, может отвечать на вопрос либо «Yes», либо «No».

Андрей не хочет, чтобы преподаватели узнали, что он ищет свои знания по языку Python, поэтому он должен задать не более, чем $$$60$$$ вопросов, чтобы никто ничего не заподозрил.

Помогите Андрюше отгадать загаданную точку в паркете не более чем за $$$60$$$ вопросов.

Сначала на вход вашей программе подается одно целое число $$$n$$$ — количество точек на стороне квадрата, в котором нужно искать точку($$$1 \le n \le 10^8$$$).

После этого ваша программа может делать запросы:

Для того, чтобы спросить, является ли точка с натуральными координатами $$$(x, y)$$$ искомой (запрос типа 1), нужно вывести в выходной поток в отдельной строке «? 1 $$$x$$$ $$$y$$$» .

Для того, чтобы спросить, лежит ли искомая точка на отрезке с концами в натуральных точках $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$ (запрос типа 2), нужно вывести в выходной поток в отдельной строке «? 2 $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$» .

Для того, чтобы спросить, лежит ли искомая точка внутри треугольника с вершинами в натуральных точках $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$(x_3, y_3)$$$ (запрос типа 3), нужно вывести в выходной поток в отдельной строке «? 3 $$$x_1$$$ $$$y_1$$$ $$$x_2$$$ $$$y_2$$$ $$$x_3$$$ $$$y_3$$$» .

В ответ на запрос во входном потоке будет записана строка «Yes», если ответ положительный, или «No» в противном случае.

В любом запросе координаты точек должны быть натуральными числами и не должны превосходить $$$10^9$$$.

Если ваша программа сделает более $$$60$$$ запросов или задаст некорректный запрос (например, запросите вырожденный треугольник), она получит любой вердикт отличный от «Accepted».

Определив, в какой точке плоскости находится заначка со знаниями языка Python, ваша программа должна вывести в выходной поток «! $$$x$$$ $$$y$$$», где $$$(x, y)$$$ — координаты искомой точки.

Гарантируется, что загаданная точка имеет натуральные координаты, а также загаданная точка фиксированная и не будет меняться в ходе тестирования вашей программы.