В глубинах Застывшего Мира, где неподвижно даже время, скрывается Линк. Силы тьмы похитили его, и только Зельда, храбрая принцесса Хайрула, может спасти его.
Зельда обладает древним артефактом — Жезлом Трифа, который при активации загорается огнем, если герой Линк находится на расстоянии не больше $$$2d$$$ от жезла. Правда, Зельда читала инструкцию по использованию Жезла очень давно и уже забыла, чему равно $$$d$$$, она только помнит, что $$$d$$$ целое и лежит в отрезке от $$$1$$$ до $$$10^5$$$.
Сейчас Зельда находится в точке $$$(0, 0)$$$ и знает, что Линк находится на расстоянии не больше $$$d$$$ от нее, то есть если активировать жезл, то он загорится.
Линк спрятан силами тьмы в некоторой точке $$$(x_0, y_0)$$$ с необязательно целыми координатами, причем $$$-10^5 \le x_0, y_0 \le 10^5$$$. Зельда хочет как можно быстрее найти его. Для этого она может не более $$$400$$$ раз перейти в произвольную точку $$$(x, y)$$$ ($$$-10^6 \le x, y \le 10^6$$$) координатной плоскости и активировать Жезл, чтобы проверить, находится ли Линк на расстоянии не больше $$$2d$$$.
Помогите Зельде найти координаты Линка с абсолютной погрешностью каждой из координат точки не более $$$10^{-3}$$$.
Это интерактивная задача.
Взаимодействие с интерактором проходит в виде запросов со стороны вашей программы и ответов со стороны интерактора. Каждый запрос представляется в виде «? $$$x$$$ $$$y$$$», что означает перейти в точку с вещественными координатами $$$x$$$ и $$$y$$$ ($$$-10^6 \le x, y \le 10^6$$$) и активировать Жезл Трифа. В качестве ответа на запрос вы получите одну из двух строк:
Чтобы вывести ответ на задачу, напечатайте «! $$$x_0$$$ $$$y_0$$$», где $$$x_0$$$ и $$$y_0$$$ — предполагаемые координаты места, где спрятан Линк. Этот вывод не учитывается в количестве запросов.
Если в какой-то момент ваша программа превышает лимит в $$$400$$$ запросов или вы выводите запрос в точке за пределами доступной области, интерактор завершится с вердиктом WA (Wrong Answer).
Не забывайте после каждого запроса выводить символ перевода строки ('{\}n') и сбрасывать буфер вывода, чтобы интерактор получил ваш запрос. Это можно сделать с помощью std::cout.flush() в C++, System.out.flush() в Java и sys.stdout.flush() в Python, а также аналогичными командами в других языках. Если ваша программа не сбрасывает буфер вывода, она получит вердикт TL (Time Limit Exceeded) или IL (Idleness Limit Exceeded).
? 1 0 ? 3 0 ? -1 1 ? 1 1 ? 0 2 ? 2 1 ? 2 1.000001 ? 0 -1.000001 ! 1 0
YES YES NO YES NO YES NO NO
В первом примере из условия одно из возможных значений $$$d$$$ равно $$$1$$$. Тогда если мы находимся на расстоянии не больше $$$2$$$ от $$$(1, 0)$$$, мы получаем ответ YES, а иначе NO.