Dette er et interaktivt problem.

Little Cyan Fish har et hemmelig heltall $a$ ($1 \le a \le 100$). Du må finne dette heltallet.

I én spørring velger du et heltall $x$. Little Cyan Fish forteller deg om $x$ er lik det hemmelige heltallet hans. Finn det hemmelige heltallet med høyst $100$ spørringer.

Interaksjon

For å gjøre en spørring, skriv ut en linje i følgende format: "$?\ x$", der $x$ er et heltall ($1 \le x \le 100$). Som svar på spørringen vil du få ett enkelt ord yes eller no, som betyr henholdsvis at $x = a$ eller $x \ne a$. Du må sørge for at antallet spørringer du gjør ikke overstiger $100$.

For å rapportere svaret, skriv ut en linje i følgende format: "$!\ x$", der $x$ er det hemmelige heltallet. Å rapportere svaret teller ikke som en spørring. Å motta yes avslutter ikke interaksjonen: du må fortsatt rapportere svaret. Programmet ditt må avsluttes umiddelbart etter at svaret er rapportert. Etter å ha skrevet ut en spørring eller rapportert svaret, ikke glem å skrive ut et linjeskifttegn og tømme utdatastrømmen (flush).

I dette problemet er interaktoren ikke adaptiv. Det hemmelige heltallet er fastsatt før interaksjonen begynner og endres ikke under interaksjonen.

Eksempler

Inndata 1

no

no

yes

Utdata 1

? 1

? 2

? 3

! 3

Merk

I det første eksempelet er det hemmelige heltallet $3$. Spørringene med $x = 1$ og $x = 2$ mottar no, og spørringen med $x = 3$ mottar yes. Løsningen rapporterer deretter ! 3.

I det andre eksempelet er det hemmelige heltallet $1$. Den første spørringen mottar yes, og løsningen rapporterer ! 1.

Testverktøy: Et testverktøy er tilgjengelig for å hjelpe deltakerne med å utvikle og teste løsningene sine. Du kan laste ned dette verktøyet fra vedleggene. Å kjøre verktøyet med valget -h beskriver hvordan det brukes. Verktøyet sjekker interaksjonen og det rapporterte svaret, men håndhever ikke tids- eller minnegrensen.