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

Арифметическая прогрессия — такая последовательность целых чисел, что разность каждого элемента и предшествующего ему ($$$x_i - x_{i - 1}$$$, где $$$i \ge 2$$$) постоянна (это значение называется разностью арифметической прогрессии).

Тем самым, арифметическая прогрессия — последовательность вида $$$x_i = x_1 + (i - 1) d$$$, где $$$d$$$ — разность арифметической прогрессии.

Загадан список из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$.

Гарантируется, что все элементы $$$a_1, a_2, \ldots, a_n$$$ лежат в диапазоне от $$$0$$$ до $$$10^9$$$, включительно.

Этот список особенный: если отсортировать его в возрастающем порядке, то он превратится в арифметическую прогрессию с положительной разностью ($$$d > 0$$$). Например, список $$$[14, 24, 9, 19]$$$ удовлетворяет этому условию, так как после сортировки он становится равен $$$[9, 14, 19, 24]$$$, что может быть получено с помощью $$$x_n = 9 + 5 \cdot (n - 1)$$$.

Вместе со списком, у вас есть устройство с практически разряженной батареей, которым вы можете воспользоваться, чтобы выполнить не более $$$60$$$ запросов следующих двух видов:

• Вы называете значение $$$i$$$ ($$$1 \le i \le n$$$), а устройство отображает значение $$$a_i$$$.
• Вы называете значение $$$x$$$ ($$$0 \le x \le 10^9$$$), а устройство отображает $$$1$$$, если есть элемент со значением строго больше $$$x$$$, и отображает $$$0$$$ иначе.

Вы можете использовать это устройство, чтобы задать не более $$$60$$$ запросов. Ваша задача — узнать наименьший элемент и разность заданной арифметической прогрессии, то есть значения $$$x_1$$$ и $$$d$$$ из ее определения. Обратите внимание, что список $$$a$$$ не упорядочен по возрастанию.

Взаимодействие начинается с одного целого числа $$$n$$$ ($$$2 \le n \le 10^6$$$), количества элементов в списке.

Затем вы можете делать запросы двух видов:

• "? i" ($$$1 \le i \le n$$$) — чтобы узнать значение $$$a_i$$$.
• "> x" ($$$0 \le x \le 10^9$$$) — чтобы проверить есть ли элемент больший $$$x$$$.

После вывода запроса, считайте ответ $$$r$$$ на него как целое число.

• Для запроса первого типа, $$$r$$$ удовлетворяет $$$0 \le r \le 10^9$$$.
• Для запроса второго типа, $$$r$$$ равен $$$0$$$ или $$$1$$$.
• В случае, если вы сделаете более $$$60$$$ запросов или нарушите ограничения на числа в запросе, то в ответ вы получите $$$r = -1$$$.
• Если ваша программа завершится после получения -1, то вы получите вердикт «Неправильный ответ». В противном случае, вердикт может быть любым, так как ваша програма продолжит читать из закрытого потока.

После того как вы выясните значение наименьшего элемента ($$$x_1$$$) и разность прогрессии ($$$d$$$), выведите:

• "! $$$x_1$$$ $$$d$$$"

И завершите программу после этого. Этот запрос не учитывается относительно ограничения в $$$60$$$ запросов.

После вывода любого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Hacks

Для взломов используйте следующий формат:

Первая строка должна содержать одно целое число $$$n$$$ ($$$2 \le n \le 10^6$$$) — количество элементов в списке.

Вторая строка должна содержать $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — элементы списка.

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