题目描述

これは対話式の問題です。

あなたの課題は、秘密のパスワード $S$ を当てることです。 パスワードは長さ $L$ 以下の空でない文字列であり、パスワードの各文字は英小文字 (a, b, ..., z)、英大文字 (A, B, ..., Z)、数字 (0, 1, ..., 9) のいずれかです。

秘密のパスワード $S$ を当てるために、クエリを送ることができます。 クエリは、上述のパスワードの要件を満たす文字列 $T$ からなり、送られたクエリに対しては $S$ と $T$ の編集距離 (考慮する操作は文字の削除、挿入、置換) が回答されます。 送ることができるクエリの数は $Q$ 個までです。

注記: 編集距離 (考慮する操作は文字の削除、挿入、置換) の定義については、Wikipedia 内のこちらのページ を参照してください。

Input & Output Format

クエリを送るには、標準出力に以下のように出力せよ (末尾に改行を入れること)。

? $T$

ここで、文字列 $T$ はパスワードの要件を満たさなければならない。

クエリへの回答 $ans$ は、標準入力から以下の形式で与えられる。

$ans$

秘密のパスワード $S$ を特定したら、標準出力に以下のように出力せよ (末尾に改行を入れること)。

! $S$

そして、すぐにプログラムを終了させよ。

题目大意

本题为交互题。

你需要猜测一个密码 $S$。密码是一个非空字符串，其长度至多为 $L$。密码中的字符可以是小写字母、大写字母和数字（a, b, ……, z, A, B, ……, Z, 0, 1, ……, 9）。

为了猜中密码，你可以进行至多 $Q$ 次询问。在一次询问中，你需要提出一个合法的密码 $T$，交互器会返回 $S$ 与 $T$ 之间的编辑距离。

对于编辑距离（编辑操作包含移除、插入和替换）的定义，可以参考百度百科。

交互格式

询问时，应在新的一行向标准输出打印如下内容，表示你提出的密码为 $T$：

? T

字符串 $T$ 必须为合法的密码。

交互器会从标准输出返回一行一个整数表示答案 $S$ 与 $T$ 之间的编辑距离。

如果已经确定了密码的内容，应在新的一行向标准输出打印如下内容，表示你的答案为 $S$：

! S

随后结束程序。

交互机制

• 在每次打印内容后，应当刷新标准输出。反之评测结果可能为 TLE。
• 在输出所猜测的答案后，必须立即结束程序。其余行为均是未定义的。
• 如果所猜测的答案错误，评测结果为 WA。
• 如果询问格式有误（有可能提出的密码不合法，也有可能丢失了询问初始的 ?）、你的程序意外终止或询问次数超过了 $Q$ 次，交互器的行为都是未定义的，评测结果不一定是 WA。

数据范围

$L = 128, Q = 850$。答案 $S$ 在交互前确定。

提示

制約

• $L\ =\ 128$
• $Q\ =\ 850$
• 秘密のパスワード $S$ は、プログラムとジャッジの対話の開始前に選ばれる。

判定

• 出力のたびに標準出力を flush せよ。 これが守られない場合、ジャッジ結果が TLE となる可能性がある。
• 秘密のパスワード (とあなたが考えるもの) を出力したら、直ちにプログラムを終了させよ。これが守られない場合のジャッジ結果は未定義である。
• 不正な形式のクエリが送られた場合 (例: 送られた文字列がパスワードの要件を満たさない、出力の先頭に ? がない)、プログラムが異常終了した場合、または $Q$ 回を超えてクエリが送られた場合のジャッジ結果は未定義である (WA とは限らない)。

入出力例

以下の例において、秘密のパスワードは Atcod3rIsGreat です。

Input Output $\texttt{?\ AtcoderIsBad}$ $5$ $\texttt{?\ AtcoderIsGreat}$ $1$ $\texttt{!\ Atcod3rIsGreat}$