В стране Байтландии есть ровно $$$n$$$ городов. Страной управляет президент, а в каждом городе сидит некоторое (не обязательно одинаковое, возможно нулевое) количество министров, которое мы назовем размером министерства этого города. В любом отдельно взятом городе министры пронумерованы подряд целыми положительными числами, начиная с $$$1$$$. В подчинении у министра находятся все министры его города с меньшими номерами. Известно, что ни в каком городе не находится более $$$h$$$ министров.

Назовем важностью министра количество его подчиненных, тогда важность $$$i$$$-го министра в любом городе в точности равна $$$i - 1$$$. Чтобы члены правительства не перекладывали обязанности друг на друга, были введены следующие правила:

1. Ни один министр не знает своей важности.
2. У каждого министра есть способ связи со всеми министрами такой же важности из других городов, и только с ними.
3. У президента в каждый момент времени есть способ связи с министрами максимальной важности из каждого города, и только с ними.

Сегодня президент решил выяснить сколько всего в Байтландии министров. Для этого он может делать два типа запросов:

1. «- i x» — уменьшить размер министерства $$$i$$$-го города на $$$x$$$. В этом случае, если $$$x$$$ больше количества министров в городе, то ничего не происходит, иначе — в отставку уходят $$$x$$$ министров с максимальной важностью. Разумеется, после этого президент получает контакт нового самого важного министра города $$$i$$$, а министры из других городов теряют связь с ушедшими в отставку.
2. «? i» — спросить у самого важного министра города $$$i$$$, с каким числом министров (включая его самого) у него есть связь. Если же в городе $$$i$$$ не осталось министров, автоответчик сообщит президенту число $$$n$$$. Таким образом, в любом случае, президент узнает в ответ количество городов, в которых на данный момент есть хотя бы столько же министров, сколько и в $$$i$$$-м, включая и сам $$$i$$$-й город.

Помогите президенту определить, сколько в Байтландии министров. Даже если их количество уменьшится в процессе выяснения ответа, президент хочет знать, сколько их было изначально. Разумеется, время президента очень ценно, поэтому он успеет сделать не более $$$q$$$ описанных выше запросов.

Интерактор ожидает от вашей программы запросы трех типов: «- i x», «? i» и «! a», где $$$i$$$, $$$x$$$ и $$$a$$$ — целые числа ($$$1 \leqslant i \leqslant n$$$; $$$0 \leqslant x \leqslant h$$$). После каждого запроса должен следовать перевод строки. При несоблюдении вашей программой формата запросов, ваше решение может получить произвольный вердикт (отличный от OK).

На запрос первого типа интерактор на новой строке отвечает «OK», если операция прошла успешно, и «FAIL», если в $$$i$$$-м городе было меньше $$$x$$$ министров. На запрос второго типа интерактор также на новой строке ответит числом, равным количеству городов, в которых не меньше министров, чем в $$$i$$$-м городе.

Запрос третьего типа означает, что ваша программа готова дать ответ на задачу. Если $$$a$$$ — верный ответ, интерактор выведет «OK» и перейдет к следующему тесту данного мультитеста или завершится, если такого нет. Если ответ неверен, интерактор выводит «-1» и завершается с вердиктом WA.

Ваша программа может вывести не более $$$q$$$ запросов первого или второго типа. Запрос третьего типа (ответ на тест) в этом ограничении не учитывается. При превышении данного ограничения, интерактор выводит «-1» завершается с вердиктом WA.

Обратите внимание, что завершение интерактора означает, что следующие тесты данного мультитеста будут пропущены. Чтобы не получить при этом вердикт TL или IL, при прочтении из ввода значения «-1» ваша программа должна завершить свою работу с нулевым кодом возврата.

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

Баллы за тест начисляются только если на каждом из $$$t$$$ наборов данных был дан верный ответ без превышения лимита запросов. В таком случае количество баллов за каждый набор данных вычисляется по формуле $$$$$$\mathtt{score}\left(c, j\right) = \max\left(1,\: 4 - \left\lfloor\max\left(0, \frac{c - j}{\gamma}\right)\right\rfloor\right)$$$$$$ где $$$c$$$ — количество итераций, сделанное вашей программой, $$$j$$$ — количество итераций, сделанное решением жюри, а $$$\gamma$$$ — отдельно заданный для каждого теста параметр.

В качестве финальной оценки за тест берется минимум из $$$t$$$ оценок его наборов данных.