Score : 800 points

Problem Statement

This is an interactive task.

Snuke has a favorite positive integer, N. You can ask him the following type of question at most 64 times: "Is n your favorite integer?" Identify N.

Snuke is twisted, and when asked "Is n your favorite integer?", he answers "Yes" if one of the two conditions below is satisfied, and answers "No" otherwise:

  • Both n \leq N and str(n) \leq str(N) hold.
  • Both n > N and str(n) > str(N) hold.

Here, str(x) is the decimal representation of x (without leading zeros) as a string. For example, str(123) = 123 and str(2000) = 2000. Strings are compared lexicographically. For example, 11111 < 123 and 123456789 < 9.

Constraints

  • 1 \leq N \leq 10^{9}

Input and Output

Write your question to Standard Output in the following format:

? n

Here, n must be an integer between 1 and 10^{18} (inclusive).

Then, the response to the question shall be given from Standard Input in the following format:

ans

Here, ans is either Y or N. Y represents "Yes"; N represents "No".

Finally, write your answer in the following format:

! n

Here, n=N must hold.

Judging

  • After each output, you must flush Standard Output. Otherwise you may get TLE.
  • After you print the answer, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
  • When your output is invalid or incorrect, the behavior of the judge is undefined (it does not necessarily give WA).

Sample

Below is a sample communication for the case N=123:

Input Output
? 1
Y
? 32
N
? 1010
N
? 999
Y
! 123
  • Since 1 \leq 123 and str(1) \leq str(123), the first response is "Yes".
  • Since 32 \leq 123 but str(32) > str(123), the second response is "No".
  • Since 1010 > 123 but str(1010) \leq str(123), the third response is "No".
  • Since 999 \geq 123 and str(999) > str(123), the fourth response is "Yes".
  • The program successfully identifies N=123 in four questions, and thus passes the case.