Побег от зомби
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Как вы знаете, в Академии Невермор живут зомби, которые ходят по территории академии, представленной в виде декартовой плоскости. Зомби — мертвые создания, поэтому очень медлительные и несообразительные. Передвигаются они только параллельно осям координат, и расстояние $$$d$$$ в одном направлении они проходят за $$$d^2$$$ секунд (при этом $$$d$$$ должно быть целым). Заметьте, что после прохождения расстояния $$$d$$$ зомби должен сменить направление движения, чтобы не сойти с ума.

К примеру, валидный путь зомби может выглядеть так:

$$$$$$(0,0)\to(2,0)\to(2,1)\to(-1,1)\to(-1,-1)\to(0,-1)$$$$$$

И такой маршрут зомби преодолеет за $$$2^2+1^2+3^2+2^2+1^2=19$$$ секунд.

Ясно, что маршрут до одной и той же точки может занять у зомби разное количество времени. К сожалению местных жителей, зомби уже научились преодолевать расстояния за оптимальное время. Тогда за $$$f(x, y)$$$ обозначим минимальное время, за которое зомби может добраться до точки $$$(0, 0)$$$ из точки $$$(x, y)$$$.

Вы решили проверить свою смекалку и узнать, насколько хорошо вы ориентируетесь на местности. Уэнсдей прекрасно знает характер зомби, и она согласилась играть с вами на таких условиях:

Уэнсдей загадывает точку $$$(x_0, y_0)$$$ на плоскости с целыми координатами (в неё она поставит зомби). После этого вы можете задавать ей следующие вопросы:

- «? $$$\Delta x$$$ $$$\Delta y$$$» — после этого вопроса Уэнсдей передвинет зомби на вектор $$$(\Delta x, \Delta y)$$$ на плоскости и сообщит вам, сколько времени вы выиграли, когда передвинули зомби на такой вектор: формально, она сообщит вам $$$f(x + \Delta x, y + \Delta y) - f(x, y)$$$, где $$$(x, y)$$$ — координаты зомби до этого хода. После этого хода зомби переместится на указанный вами вектор.

Естественно, Уэнсдей согласилась играть с вами в эту игру не просто так: вам нужно угадать точку, загаданную Уэнсдей, иначе она скормит вас зомби.

Протокол взаимодействия

Взаимодействие с интерактором проходит в виде запросов со стороны вашей программы и ответов со стороны интерактора. Вы можете выполнить действие, описанное в условии, не более $$$100$$$ раз.

Чтобы переместить точку, выведите строку в формате «? $$$\Delta x$$$ $$$\Delta y$$$», после чего загаданная точка переместится на вектор $$$(\Delta x, \Delta y)$$$ ($$$|\Delta x|, |\Delta y| \leq 2 \cdot 10^9$$$). Интерактор в ответ выведет на отдельной строке ответ Уэнсдей.

Чтобы вывести ответ на задачу, выведите строку «! $$$x$$$ $$$y$$$», где в качестве $$$x$$$ и $$$y$$$ должны быть текущие координаты точки. Этот вывод не учитывается в количестве запросов. После этого интерактор выведет вердикт — «You win», если ваше предположение верно, и «Your brains will be eaten» в противном случае. Если ваш ответ был неверен, ваше решение получит вердикт WA (Wrong Answer), а интерактор завершится. Во избежание получения некорректных вердиктов, считав информацию о том, что выведенный ответ неверен, ваше решение тоже должно завершиться.

Гарантируется, что исходная точка, загаданная Уэнсдей, имеет целые координаты, по модулю не превосходящие $$$10^9$$$.

Если в какой-то момент ваша программа превышает лимит в $$$100$$$ запросов, ваша программа завершится с вердиктом WA.

Если в какой-то момент координаты точки, загаданной Уэнсдей, по модулю превысили $$$8\cdot10^9$$$, то она ответит вам $$$-1$$$ и вы получите вердикт WA.

Важно: не забывайте после каждой выведенной строки сбрасывать буфер вывода, чтобы интерактор получил ваш запрос. Это можно сделать с помощью std::cout.flush() в C++, System.out.flush() в Java и sys.stdout.flush() в Python, а также аналогичными командами в других языках. Если ваша программа не сбрасывает буфер вывода, она получит вердикт TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded).

Пример

Входные данные

    ? 2 -1

    ? -2 0

    ? -1 1

    ? 1 0

    ! 1 2

Выходные данные

    3

    -4

    0

    1

    You win

Примечание

В первом примере изначально загадана точка $$$(1, 2)$$$, и в результате запросов она двигается таким образом:

$$$$$$(1,2)\to(3,1)\to(1,1)\to(0,2)\to(-1,-1)\to(1,2)$$$$$$