Задача E. Encrypted phone ≡

Условие

Данная задача является интерактивной.

В наказание за то, что ученик Алексей сидел на уроке в телефоне, учитель установил на него пароль. Паролем является последовательность из N целых положительных чисел X_i, выбранных учителем. Но он решил не тратить время на придумывание всех чисел, поэтому воспользовался генератором случайных чисел.

Чтобы разблокировать свой телефон, Алексей должен разгадать эту последовательность. Для этого он может задать учителю не более Q вопросов — делится ли i-ое число в последовательности (нумерация чисел от 1 до N) на число d.

Помогите Алексею вернуть доступ к телефону, он уже полностью раскаялся в своём поведении на уроке и больше так делать не будет.

Формат входных данных

Первая строка содержит одно целое число N — длина последовательности чисел.

Гарантируется, что числа в последовательности не изменяются в зависимости от вопросов Алексея.

Гарантируется, что последовательность чисел сгенерирована случайным образом.

Формат выходных данных

Чтобы сообщить учителю свой ответ, выведите символ "!", а затем N разгаданных чисел X_i через пробел. Обратите внимание, что "!" и X₁ также должны быть разделены пробелом. После этого решение должно немедленно завершиться.

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

Для каждого теста жюри зафиксировало число Q — максимальное количество вопросов, которые можно задать учителю. Гарантируется, что Q вопросов достаточно, чтобы решить задачу. Это число не сообщается программе-решению. Если решение делает более Q вопросов, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы задать вопрос программа-решение должна вывести строку вида "? i d", где i (1 ≤ i ≤ N) и d (1 ≤ d ≤ 5000) — целые числа. В ответ на вопрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, делится ли i-ое число в загаданной последовательности на число d.

Каждый вопрос и вывод ответа должен заканчиваться символом перевода строки \n, а также необходимо выполнить сброс буфера:

Ограничения

100 ≤ N ≤ 400

1 ≤ X_i ≤ 5000

Q = min(150 ⋅ N, 5 ⋅ 10⁴)

Пояснение к примерам

Обратите внимание, что первый тест не подходит под ограничения задачи (N = 2).

Он сделан лишь для демонстрации протокола взаимодействия программы-решения и программы жюри.

При проверке первого теста Q = 2000.

Примеры тестов

2

Yes

No

Yes

No

No

Yes

Yes

Yes

Yes

Okay

? 1 3

? 1 5

? 1 7

? 1 11

? 1 13

? 1 4998

? 2 128

? 2 512

? 2 4096

! 4998 4096