Problem E. Encrypted phone

Author:N. Grebenyuk, A. Usmanov. Translation: A. Logutova.   Time limit:2 sec
Input / output:interactive   Memory limit:256 Mb

Statement

This is an interactive problem.

As a punishment for Aleksey using his cellphone in the classroom, the teacher locked Aleksey's device with a password. This password is a sequence of N unsigned integers Xi, chosen by the teacher. However, the teacher did not want to waste his time for thinking up all numbers of the sequence. Therefore, he used a random number generator.

To unlock his device, Aleksey needs to guess the sequence. He can ask the teacher no more than Q questions: whether Xi is divisible by d. All numbers in the sequence are indexed from 1 to N.

Help Aleksey to regain access to his cellphone. He has already regretted his bad behavior during the class. He'll never do it again.

Input format

The first line contains one integer N — the length of the sequence.

It is guaranteed that the sequence is randomly generated before all Aleksey's questions and cannot be changed after that.

Output format

To give your answer to the teacher you have to print character "!" (without quotes), then print N space-separated guessed numbers Xi. Note that "!" and X1 should be separated by a space too. Your program should terminate immediately after you gave the answer.

Interaction

Jury has fixed a number Q for each test — the maximum amount of questions, which you can ask the teacher. It is guaranteed that Q questions are enough to solve the problem. Q won't be given to your program as an input. If your solution asks more than Q questions, it will get "Wrong answer" for this test.

To ask a question your program has to print line "? i d" (without quotes), i (1 ≤ i ≤ N) and d (1 ≤ d ≤ 5000) are integers. Jury program gives your solution line "Yes" if Xi is divisible by d or "No" if it's not.

In the end of each question you have to print newline character \n and flush output buffer. To flush the buffer you can use (just after printing):

Language C++ Pascal Java Python
Command cout.flush() flush(output) System.out.flush() stdout.flush()

Constraints

100 ≤ N ≤ 400

1 ≤ Xi ≤ 5000

Q = min(150 ⋅ N, 5 ⋅ 104)

Sample tests explanation

Note that the first test doesn't satisfy the constraints of the problem (N = 2).

It was created only to demonstrate interaction of solution program and jury program.

Q = 2000 for the first test.

Sample tests

No. Standard input Standard output
1
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

0.093s 0.009s 13