시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 512 MB 18 1 1 100.000%

문제

We have chosen an integer $m$ between $1$ and $n$. Your task is to guess it, and you have to do no more queries than necessary for this $n$. Each of your queries must be an integer which has no more than $n$ digits in its decimal notation. The answer to query $x$ is the remainder $x \bmod m$.

입력

In the beginning, your program will receive one integer $n$ ($1 \le n \le 10^6$).

Then your program will receive the answers to the queries. Each answer is an integer.

출력

Your program can make queries in the form "? $\mathit{number}$". When you think you know the answer, you should print "! $\mathit{guess}$", and then terminate your program immediately. Don't forget to output the line break and flush the output. To do so, you can use the following instructions:

  • fflush(stdout) in C++;
  • System.out.flush() in Java;
  • stdout.flush() in Python;
  • flush(output) in Pascal.

예제 입력 1

2
1

예제 출력 1

? 79
! 2

예제 입력 2

3
0
0
0

예제 출력 2

? 42
? 777
? 8
! 1

힌트

You are not prohibited to output leading zeroes, but the checking program counts them when determining the length of the number. For example, if $n = 3$, query "$001$" is valid, but "$0001$" is invalid.

The second sample just demonstrates the interaction format, guessing can be done in smaller number of queries.

채점

  • 예제는 채점하지 않는다.