Вгадайте число

Це інтерактивна задача. Це означає, що під час тестування разом з вашим розв'язком буде запускатися програма журі (далі - інтерактор). Вашій програмі потрібно "спілкуватися" з нею. Для мов C++ та Python наданий шаблон, як правильно комунікувати.

Інтерактор загадав певне число від $1$ до $100$. Вам потрібно вгадати це число. Ви можете давати числа інтерактору, а він буде відповідати, чи число, яке він загадав, більше чи менше за те, що ви йому передали.

Наприклад, припустимо, інтерактор загадав число $83$. Якщо ви йому передасте число $30$, то він скаже «більше». Якщо число $90$, то скаже «менше». Якщо $83$, то «рівне».

Вам потрібно за $6$ питань зрозуміти, що це за число.

Вам може бути корисно прочитати про двійковий (бінарний) пошук.

Нижче можна знайти коди на різних мовах, які отримують 6 балів.

Interaction

Вам потрібно робити запитати у такому форматі:

«? x». Де $x$ ($1\le x\le 100$) — число, яке ви хочете передати інтерактору. Ви можете це робити не більше $100$ разів. Вам потрібно це вивести, а потім вивести символ нового рядка. Після цього обов'язково потрібно виконати операцію flush. Вам потрібно зчитати відповідь. Якщо число, яке загадав інтерактор, більше за ваше, то ви зчитаєте число $1$. Якщо менше, то $-1$. Якщо ваше число є тим числом, що загадав інтерактор, то ви зчитаєте $0$.

Операцію flush у різних мовах потрібно виконувати так:

• fflush(stdout) або cout.flush() в C++;

• System.out.flush() в Java;

• flush(output) в Pascal;

• stdout.flush() в Python;

• для всіх інших мов вам потрібно дивитися документацію самостійно.

Після того, як ви будете впевнені у тому, яке число загадав інтерактор, вам потрібно вивести «! x», символ нового рядка та виконати операцію flush.

Examples

1
-1
0

? 30
? 90
? 83
! 83

Scoring

Нехай $q$ — максимальна кількість питань серед усіх тестів.

Якщо $q>100$, то ви отримаєте $0$ балів.

Інакше, ви отримаєте $\min (106-q,100)$ балів.