1. Отгадай число
ограничение по времени на тест
1 с
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача немного необычна — в ней вам предстоит реализовать интерактивное взаимодействие с тестирующей системой. Это означает, что вы можете делать запросы и получать ответы в online-режиме. Обратите внимание, что ввод/вывод в этой задаче — стандартный (то есть с экрана на экран). После вывода очередного запроса обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию fflush(stdout), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.

В этой задаче вам предстоит в интерактивном режиме угадать число x, которое загадала тестирующая система. Про загаданное число известно, что оно целое и лежит в границах от 1 до 1 000 000 включительно.

Вы можете делать запросы к тестирующей системе, каждый запрос — это вывод одного целого числа от 1 до 1 000 000. Есть два варианта ответа тестирующей системы на запрос:

  • строка «<» (без кавычек), если загаданное число меньше числа из запроса;
  • строка «>=» (без кавычек), если загаданное число больше либо равно числу из запроса.

В случае, если ваша программа считает, что определила загаданное число, выведите строку вида «! x», где x — это ответ, и завершите работу своей программы.

Вашей программе разрешается сделать не более 25 запросов (не считая вывода ответа).

Входные данные

Для чтения ответов на запросы программа должна использовать стандартный ввод.

Входные данные будут содержать ответы на запросы, то есть строки вида «<» и «>=». i-я из этих строк является ответом системы на i-й запрос. После того, как ваша программа угадала число, выведите «! x» (без кавычек), где x — это ответ, и завершите работу своей программы.

Тестирующая система даст вашей программе прочитать ответ на запрос из входных данных только после того, как ваша программа вывела соответствующий запрос системе и выполнила операцию flush.

Выходные данные

Для осуществления запросов программа должна использовать стандартный вывод.

Ваша программа должна выводить запросы — целые числа xi (1 ≤ xi ≤ 106) по одному в строке. После вывода каждой строки программа должна выполнить операцию flush.

Каждое из значений xi обозначает очередной запрос к системе. Ответ на запрос программа сможет прочесть из стандартного ввода. В случае, если ваша программа угадала число, выведите строку вида «! x» (без кавычек), где x — ответ, и завершите работу программы.

Примеры
Входные данные
>=
<
>=
>=
<
<
Выходные данные
8
20
11
12
13
16
! 12
Входные данные
<
<
>=
Выходные данные
123
70
30
! 43
Примечание

В первом примере загадано число 12. В приведённом примере общения программы с интерактором делается шесть запросов. Обратите внимание, что мы уже однозначно знаем ответ после первых пяти запросов, но ничто не запрещает нам сделать лишний запрос просто так (пока их количество не превысило 25).

Во втором примере загадано число 43. После первых трёх запросов есть ещё много подходящих чисел, но никто не запрещает нам попытаться угадать ответ.