Это интерактивная задача. Вы должны использовать flush после каждой строки вывода. В C++ следует использовать функцию fflush(stdout), в Java — System.out.flush(), в Python — sys.stdout.flush(), в Pascal — flush(output).

Есть $$$n$$$ карточек, каждая из которых с одной стороны покрашена в серый цвет, а с другой — в синий или в красный. Карточки выложены в ряд серой стороной вверх таким образом, что сначала идут все «синие» карточки, а затем — все «красные» карточки. Будем считать, что карточки занумерованы в порядке их размещения в ряду (то есть номер любой синей карточки меньше, чем номер любой красной карточки).

Никанор предложил Евлампию угадать наибольший номер, который имеет синяя карточка.

Евлампий должен действовать по следующим правилам:

• За один ход Евлампий может указать на любую карточку, и она будет перевёрнута (открыта).
• Если открытая карточка окажется синей, то все ещё не перевёрнутые карточки с меньшими номерами также будут открыты.
• Если открытая карточка окажется красной, никакие другие карточки не открываются.
• Если Евлампий готов сообщить ответ, он называет наибольший номер, который (по его мнению) имеет синяя карточка, после чего игра прекращается. Ответ не считается ходом.
• Евлампий может совершить не более $$$m$$$ ходов. Однако если Евлампий откроет вторую красную карточку, он более не сможет совершить ни одного хода. После того как все ходы исчерпаны, Евлампий должен сообщить ответ.
• Евлампий выиграет, если угадает наибольший номер, который имеет синяя карточка.

Ваша задача — сыграть за Евлампия с программой жюри. Вы должны сообщать программе целое число из диапазона от $$$1$$$ до $$$n$$$ — номер карточки, которую следует открыть. В ответ программа жюри сообщит вам цвет карточки: $$$blue$$$, если карточка синяя, и $$$red$$$, если карточка красная.

Когда вы решите, что можете назвать наибольший номер $$$b$$$, который имеет синяя карточка, отправьте программе жюри сообщение «$$$! \, \, b$$$» (без кавычек), где вместо $$$b$$$ будет записан наибольший номер, который имеет синяя карточка.

Гарантируется, что имеется хотя бы одна синяя карточка и хотя бы одна красная карточка.

Взаимодействие с интерактором начинается с чтения чисел $$$n$$$ и $$$m$$$.

Затем ваша программа может сделать не более $$$m$$$ запросов. Каждый запрос — одно целое число $$$p$$$ из диапазона от $$$1$$$ до $$$n$$$.

Каждый запрос должен завершаться концом строки и сбросом буфера (с помощью операции flush).

После каждого запроса ваша программа должна прочитать ответ жюри. Это будет либо строка $$$red$$$, если карточка $$$\#p$$$ красная, и строка $$$blue$$$, если карточка $$$\#p$$$ — синяя.

Когда ваша программа будет готова сообщить ответ, она должна вывести сообщение «$$$! \, \, b$$$» (без кавычек), где $$$b$$$ $$$(1 \le b \le n)$$$ — наибольший (по вашему мнению) номер синей карточки.

Интерактор не адаптивен: ответ известен заранее и не зависит от запросов программы участника.

Интерактор учитывает как ход любой допустимый запрос, даже если это номер уже открытой карточки.

Если ваша программа попытается совершить более $$$m$$$ запросов, она будет пытаться читать из закрытого потока данных.