Это интерактивная задача.

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

Таким образом, за один запрос Рудольф может назвать два числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq n$$$), а Бернард покажет, сколько различных символов содержится в позициях от $$$l$$$ до $$$r$$$ загаданной строки. Когда Рудольф посчитает, что знает достаточно информации о загаданной строке, он должен назвать, сколько различных подстрок содержит эта строка.

Помогите Рудольфу правильно посчитать количество различных подстрок не более чем за $$$32768$$$ запросов.

Можно сделать не более $$$32768$$$ запросов о количестве различных символов на подстроке. Каждый запрос должен иметь вид '? l r', где $$$l$$$ и $$$r$$$ — индексы исходной строки, между которыми (включительно) считается количество различных символов. Должно выполняться условие $$$1 \leq l \leq r \leq n$$$.

На каждый такой запрос будет выведено одно число $$$k$$$ — количество различных символов в подстроке, $$$1 \leq k \leq r-l+1$$$.

Ответ должен быть выведен в формате '! m', где $$$m$$$ — количество различных подстрок загаданной строки. Этот ответ не учитывается в общем количестве запросов, то есть его можно вывести даже после $$$32768$$$ запросов, указанных выше.

Гарантируется, что ответы на запросы непротиворечивы, то есть существует хотя бы одна строка, соответствующая всем ответам. Обратите внимание, что Бернард использует английский алфавит, то есть загаданная строка содержит не более $$$26$$$ различных символов.

Интерактор не является адаптивным, то есть загаданная строка не меняется по мере поступления запросов.