题目描述

これはインタラクティブな問題です。

すぬけくんはお気に入りの正の整数 $N$ を持っています。あなたは 「$n$ はお気に入りの正の整数か？」と最大 $64$ 回すぬけくんに質問することができます。 $N$ を特定してください。

すぬけくんはひねくれ者なので「$n$ はお気に入りの正の整数か？」と質問されたとき、$n$ が以下の $2$ つの条件のどちらかを満たすとき Yes と、それ以外のとき No と答えます。

• $n\ \leq\ N$ かつ $str(n)\ \leq\ str(N)$を満たす
• $n\ >\ N$ かつ $str(n)\ >\ str(N)$ を満たす

ここで、$str(x)$ は正の整数 $x$ を十進表記(先頭に $0$ をつけない)の文字列として表したものです。例えば $str(123)\ =$ 123，$str(2000)$ = 2000 です。 なお、この問題において文字列同士は辞書順で比較されます。例えば 11111 $<$ 123，123456789 $<$ 9 が成立します。

Input & Output Format

各質問は、標準出力に以下の形式で出力せよ：

? $n$

ここで $n$ は $1$ 以上 $10^{18}$ 以下の整数でなければならない。

次に、質問の答えが標準入力から以下の形式で与えられる：

$ans$

ここで $ans$ は Y または N である．Y ならば、質問の答えが Yes であることを、N ならば No であることを示す。

最後に、答えを以下の形式で出力せよ：

! $n$

ここで $n=N$ でなくてはならない。

题目大意

交互题。

给定一个数字$N$，要你通过若干次询问得到$N$。

一次交互格式类似于$?~x$，其中$x$是你询问的数字，交互库会返回答案$Y$或者$N$，分别表示$Yes$和$No$。

返回$Y$当且仅当满足下述条件中的一个：

• $x \leqslant N$并且$str(x) \leqslant str(N)$
• $x > N$并且$str(x) > str(N)$

其中$str(x)$的含义是将十进制整数$x$转成字符串，字符串比较按字典序比较。下面这行代码则是一个交互的示例，其中$s$是字符串变量，用来读取交互库返回的答案。

void query(int x){printf("? %d\n",x);fflush(stdout);scanf("%s",s);}

若找到答案，请按$!~x$的格式输出，其中$x$为你找到的数字$N$。

你最多询问 $64$ 次。

提示

制約

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

ジャッジ

• **出力のあと、標準出力を flush せよ。**従わない場合 TLE の可能性がある。
• 答えを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
• 出力の答えが間違っている場合の挙動は定義されていない(WA とは限らない)。

入出力例

これは $N=123$ のときの入出力例です。

Input Output ? 1 Y ? 32 N ? 1010 N ? 999 Y ! 123- $1\ \leq\ 123$ かつ $str(1)\ \leq\ str(123)$ なので答えは Yes です

• $32\ \leq\ 123$ ですが、$str(32)\ >\ str(123)$ なので答えは No です
• $1010\ >\ 123$ ですが、$str(1010)\ \leq\ str(123)$ なので答えは No です
• $999\ \geq\ 123$ かつ $str(999)\ >\ str(123)$ なので答えは Yes です
• $N$ は $123$ であると $4$ 回の質問で回答できたため正解となります