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

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

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

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

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

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

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

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

Интерактор принимает запросы в следующем формате:

• ? $$$a$$$ $$$d$$$ ($$$2 \le a \le 2 \cdot 10^6$$$, $$$0 \le d \lt a$$$)

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

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

Интерактор будет выдавать в ответ одно число:

• $$$0$$$, если число $$$p$$$ не сравнимо с $$$d$$$ по модулю $$$a$$$;
• $$$1$$$, в противном случае.

Когда вы готовы назвать число $$$p$$$ ($$$3 \le p \le 10^6$$$), выведите его в формате:

• ! $$$p$$$

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