Евлампий и его одногруппник Никанор вместе готовятся к экзамену.

Они собираются решить $$$n$$$ задач. Задачи занумерованы от $$$1$$$ до $$$n$$$, и решать их одногруппники будут в порядке нумерации.

Для каждой задачи $$$\#j$$$ известно время $$$t_j$$$, которое потратит на её решение Евлампий, и время $$$s_j$$$, которое потратит на её решение Никанор. Также для каждого из одногруппников известно, решил ли он задачу $$$\#j$$$ правильно или нет.

Евлампий и Никанор планируют действовать так.

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

Далее всё происходит похожим образом. Тот, кто решил некоторую задачу первым и решил её правильно, сразу же сообщает об этом товарищу. В этом случае товарищ либо прекращает решать эту задачу, либо не будет приступать к ней, если ещё не начал её решать.

Ваша задача — определить, через сколько времени одногруппники завершат решение задач (правильно или неправильно — это уж как получится), а также посчитать, сколько правильных решений будет на счету Евлампия, а сколько — на счету Никанора.

Примечание. Если Евлампий и Никанор одновременно завершают решение задачи, и у обоих это решение правильное, то это решение следует учитывать при подсчёте решений для обоих.

Ещё одно примечание. На рисунке показано, как Евлампий и Никанор решали задачи в примере входных данных.

И ещё одно примечание. На всякий случай: использование массивов или иных структур данных в этой задаче не предполагается.

Это интерактивная задача. Вы должны использовать 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$$$ запросов, она будет пытаться читать из закрытого потока данных.

У Евлампия есть список из $$$n$$$ дел, в котором для каждого дела $$$\#j$$$ указаны время $$$t_j$$$, которое требуется Евлампию, чтобы сделать это дело, и времени $$$d_j$$$, не позже которого нужно начать делать это дело.

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

Ваша задача — определить максимально возможное количество дел, которые может успеть сделать Евлампий, а также определить, какие именно это будут дела.