\begin{problem}{Мышеловы атакуют (сложная версия)}{стандартный ввод}{стандартный вывод}{2 секунды}{256 мегабайт}

\textbf{Это сложная версия задачи. Единственное различие между двумя версиями~--- ограничение на количество различных $a$ в запросах. В этой версии различных чисел $a$ в запросах может быть не более двух.}

\textbf{Это интерактивная задача.}

Вы с Эйприл О'Нил оказались в лаборатории Бакстера Стокмана и попали в ловушку. На вас наступает армия зубастых мышеловов. Единственный способ спастись: отгадать секретный код~--- число $p$ ($3 \le p \le 10^6$), с помощью которого их можно деактивировать. Эйприл работала в этой лаборатории, поэтому помнит, что число $p$ обязательно \textbf{простое}, ведь самые надёжные криптографические алгоритмы используют простые числа.

В панели управления мышеловами нашлась уязвимость. Она позволяет вам делать запросы <<Сравнимо ли число $p$ по модулю $a$ с $d$?>>. Другими словами: <<Верно ли, что $p - d$ делится нацело на $a$?>>. При этом $a$ и $d$ вы задаёте сами в каждом запросе.

Если вы нарушите формат взаимодействия или сделаете \textbf{более} $1000$ запросов или спросите \textbf{более} двух различных чисел $a$, сработает защитный протокол \textit{самоуничтожения} мышеловов, и вам не поздоровится.

Помогите Эйприл взломать панель управления и деактивировать мышеловов.


\Interaction
Вы можете сделать \textbf{не более} $1000$ запросов, включая вывод ответа.

Интерактор \textbf{не является} адаптивным, то есть число $p$ зафиксировано и \textbf{не меняется} с запросами.

Интерактор принимает запросы в следующем формате:
\begin{itemize}
\item \texttt{?} $a$ $d$ ($2 \le a \le 2 \cdot 10^6$, $0 \le d < a$)
\end{itemize}

Ваши запросы должны содержать \textbf{не более} двух различных чисел $a$.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт \texttt{Решение <<зависло>>}. Если вы пишете на \texttt{C++}, жюри советует не подключать ускорение ввода/вывода и использовать \texttt{std::endl} в качестве перевода строки.

Интерактор будет выдавать в ответ одно число:
\begin{itemize}
\item $0$, если число $p$ \textbf{не сравнимо} с $d$ по модулю $a$;
\item $1$, в противном случае.
\end{itemize}

Когда вы готовы назвать число $p$ ($3 \le p \le 10^6$), выведите его в формате:
\begin{itemize}
\item \texttt{!} $p$
\end{itemize}

После вывода секретного кода ваша программа должна немедленно завершиться, в противном случае жюри не гарантирует корректность вердикта.


\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\Note
\begin{center}
\includegraphics{mousers-pic.jpg}
\end{center}

\end{problem}

