問題 C しりとり

問題文

なんとなく暇だったのでしりとりの AI を作って AI としりとりをすることにした．しりとりとは 2 人で遊ぶゲームで，両者の間でまだ一度も発言されておらず，(最初の手番を除いて) 先頭の文字が直前の単語の最後の文字となっている単語を交互に言い合うゲームである．

今回 AI に単語の判定を実装するのが面倒だったので，単語の定義はアルファベットの小文字からなる文字列全てとした．

しかし AI が完成したあたりでしりとりをするのは面倒くさくなってきたので，プログラムを書いて自分の代わりに AI と対戦させることにした．プログラムを書くのは良いのだが目標が無いのはつまらないので，なるべく早く AI に勝つプログラムを書くことにした．すなわち，なるべく少ないやりとりで AI に不正な応答をさせるプログラムを書くのである．

なおプログラムが先手で AI が後手である．

入出力

プログラムはしりとりの単語を発言すると，AI の返答を聞くことができる． 例えば C/C++ で abc と単語を発言するには

printf("?abc\n"); fflush(stdout);

とする．次に，

scanf("%s", str);

とすると str に AI の返答が入る．

最終的に AI の誤りを指摘するには !OUT と出力すること．誤りを指摘するのは，間違った発言の直後でなければならない．誤りを指摘した時点でプログラムを終了させ，不要な出力は一切行ってはいけない．誤りの指摘が正しければプログラムは正解 (Accepted) と判定される．単語の応答が不適切であったり，AI への誤りの指摘が正しくない場合，AI の誤りを指摘しなかった場合は誤答 (Wrong Answer) と判定される．

制約

• プログラムの使って良い単語の長さは 1 文字以上 10 文字以下である．
• AI の使う単語の長さは 1 文字以上 2 文字以下である．
• プログラムは最大で 50 回まで発言することが出来る．それを超えると誤答 (Query Limit Exceeded) となる．
• AI，プログラム両者とも単語に使って良い文字はアルファベットの小文字のみである．
• AI の返答はアルファベットの小文字のみからなる．
• 最初の手番では，プログラムはどのアルファベットからしりとりを開始しても良い．

入出力例

入力例 1

以下の例はプログラムの入出力の例である．左の列がプログラムの出力，右の列がプログラムへの入力 (AI の発言) を表す．最初にプログラムは abcdefghij という単語を言っている．その応答として AI は jk と返してる．3 回目の応答の際に AI はすでに使われている jk という単語を発しているのでそれに対してプログラムは !OUT と言って AI の誤りを指摘している．

入力例 2

以下の例では，AI が aaa という単語に対して bb としりとりにならない返答をしているため !OUT と返している．

---