E. Угадай корень
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Жюри загадало многочлен $$$f(x) = a_0 + a_1 \cdot x + a_2 \cdot x^2 + \dots + a_k \cdot x^k$$$. $$$k \le 10$$$ и все $$$a_i$$$ — целые числа с $$$0 \le a_i < 10^6 + 3$$$. Гарантируется, что существует хотя бы одно $$$i$$$, для которого $$$a_i > 0$$$.

Теперь жюри просит вас найти такое $$$x_0$$$, что $$$f(x_0) \equiv 0 \mod (10^6 + 3)$$$ или сказать, что такого $$$x_0$$$ не существует.

Вы можете задать не более $$$50$$$ запросов: вы спрашиваете значение $$$x_q$$$, а жюри говорит вам значение $$$f(x_q) \mod (10^6 + 3)$$$.

Заметьте, вывод ответа не является запросом.

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

Чтобы спросить значение, выведите "? $$$x_q$$$" $$$(0 \le x_q < 10^6 + 3)$$$. Жюри ответит вам единственным числом $$$f(x_q) \mod (10^6 + 3)$$$. Если вы получите в ответ $$$−1$$$ (из-за неправильного запроса), завершите программу, чтобы избежать получения другого вердикта.

После вывода запроса не забудьте сбросить буфер, иначе вы можете получить вердикт Idleness limit exceeded. Для этого вы можете использовать:

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

Когда вы готовы вывести ответ, выведите "! $$$x_0$$$", где $$$x_0$$$ — ответ на задачу, либо $$$-1$$$ если такого значения $$$x_0$$$ не существует.

Вы можете задать не более $$$50$$$ запросов.

Формат взломов

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

В единственной строке выведите $$$11$$$ целых чисел $$$a_0, a_1, \dots, a_{10}$$$ ($$$0 \le a_i < 10^6 + 3$$$, $$$\max\limits_{0 \le i \le 10}{a_i} > 0$$$) — соответствующие коэффициенты многочлена.

Примеры
Входные данные
 
1000002

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

? 1

! 1
Входные данные
 
5

2

1

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

? 1

? 0

! -1
Примечание

Многочлен из первого примера — это $$$1000002 + x^2$$$.

Многочлен из второго примера — это $$$1 + x^2$$$.