\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{самоуничтожения} мышеловов, и вам не поздоровится.

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