Dies ist ein interaktives Problem.

Little Cyan Fish hat eine geheime ganze Zahl $a$ ($1 \le a \le 100$). Du musst diese ganze Zahl finden.

In einer Anfrage wählst du eine ganze Zahl $x$. Little Cyan Fish teilt dir mit, ob $x$ gleich seiner geheimen ganzen Zahl ist. Finde die geheime ganze Zahl in höchstens $100$ Anfragen.

Interaktion

Um eine Anfrage zu stellen, gib eine Zeile im folgenden Format aus: „$?\ x$“, wobei $x$ eine ganze Zahl ist ($1 \le x \le 100$). Als Antwort auf die Anfrage erhältst du ein einzelnes Wort yes oder no, was bedeutet, dass $x = a$ bzw. $x \ne a$ gilt. Du musst sicherstellen, dass die Anzahl der gestellten Anfragen $100$ nicht überschreitet.

Um die Antwort zu melden, gib eine Zeile im folgenden Format aus: „$!\ x$“, wobei $x$ die geheime ganze Zahl ist. Das Melden der Antwort zählt nicht als Anfrage. Das Erhalten von yes beendet die Interaktion nicht: Du musst die Antwort trotzdem noch melden. Dein Programm muss sich unmittelbar nach dem Melden der Antwort beenden. Vergiss nach der Ausgabe einer Anfrage oder dem Melden der Antwort nicht, einen Zeilenumbruch auszugeben und den Ausgabepuffer zu leeren (flush).

In diesem Problem ist der Interaktor nicht adaptiv. Die geheime ganze Zahl wird vor Beginn der Interaktion festgelegt und ändert sich während der Interaktion nicht.

Beispiele

Eingabe 1

no

no

yes

Ausgabe 1

? 1

? 2

? 3

! 3

Hinweis

Im ersten Beispiel ist die geheime ganze Zahl $3$. Die Anfragen mit $x = 1$ und $x = 2$ erhalten no, und die Anfrage mit $x = 3$ erhält yes. Die Lösung meldet daraufhin ! 3.

Im zweiten Beispiel ist die geheime ganze Zahl $1$. Die erste Anfrage erhält yes, und die Lösung meldet ! 1.

Testwerkzeug: Ein Testwerkzeug wird bereitgestellt, um den Teilnehmern bei der Entwicklung und beim Testen ihrer Lösungen zu helfen. Du kannst dieses Werkzeug aus den Anhängen herunterladen. Das Ausführen des Werkzeugs mit der Option -h beschreibt, wie es verwendet wird. Das Werkzeug überprüft die Interaktion und die gemeldete Antwort, setzt jedoch weder das Zeit- noch das Speicherlimit durch.