Жюри загадало многочлен \(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 + x^2\).
Многочлен из второго примера — это \(1 + x^2\).