Государственный переполох

В стране Байтландии есть ровно $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$ описанных выше запросов.

Это интерактивная задача. Помимо этого, каждый тест состоит из нескольких наборов данных.

В первой строке ввода дано целое число $t$ --- количество наборов данных в тесте ($1 \leqslant t \leqslant 5$). Гарантируется, что во всех тестах, кроме примера, $t = 5$.

Во второй строке ввода через пробел даны целые числа $n$, $h$ и $q$ --- количество городов, ограничение на количество министров в городе и ограничение на число запросов ($1 \leqslant n \leqslant 5000$; $1 \leqslant h \leqslant 1\\,000\\,000$; $1 \leqslant q \leqslant 24\\,000$). Эти ограничения являются общими для всех наборов данных текущего теста.

Далее $t$ раз запускается протокол взаимодействия с интерактором.

Когда ваша программа готова дать ответ на задачу, следует вывести <<! a>> (без кавычек), где $a$ --- предполагаемый ответ. После этого программа должна перейти к следующему набору данных или завершиться в соответствии с описанными в следующей секции правилами.

Это интерактивная задача. При использовании буферизованного вывода не забывайте сбрасывать буфер при выводе запросов (sys.stdout.flush() в Python, System.out().flush() в Java и std::cout.flush() в C++).

В примере из условия происходят следующие действия:

1. Первым запросом выясняется, что первое министерство --- самое маленькое, так как во всех трех городах хотя бы столько же министров.
2. Следующими двумя действиями в отставку отправляется один министр из первого города и три из второго. Из того, что $h = 3$, и ответ интерактора на запрос <<- 2 3>> --- это <<OK>>, можно сделать вывод, что во втором городе было ровно $3$ министра.
3. После этого выясняется, что во всех городах не меньше министров, чем в первом городе. Но мы знаем, что во втором их теперь $0$, а значит и в первом стало $0$, то есть было $1$.
4. Последними двумя запросами после неудачной попытки отправить трех министров из третьего города, и удачной --- двух, мы понимаем, что их было ровно $2$.

Таким образом, ответ на тест из условия --- $1 + 3 + 2 = 6$. Обратите внимание также, что $q = 6$, и было сделано ровно $6$ запросов вида <<->> и <<?>>, тогда как запрос <<!>> в это количество не входит.