Selvitä salainen luku $x$ tekemällä korkeintaan 30 kyselyä.

Lataa tehtäväpohja tästä.

Interaktio

Tehdäksesi kyselyn, tulosta kysymysmerkki sekä luku. Tämän jälkeen tulosta rivinvaihto ja varmista, että tulostepuskuri tyhjennetään.

Kyselyn vastauksena on joko rivi 10-4, jos antamasi luku on suurempi kuin $x$, tai QAQ muuten.

Kun olet saanut salaisen luvun selville, tulosta huutomerkki ja salainen luku.

Esimerkki

? 4
QAQ
? 6
10-4
! 5

Rajat

• $1 \le x \le 10^9$