Эта задача отличается от простой версии только ограничением на суммарную длину ответов

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

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

• ? l r — запросить все подстроки $$$s[l..r]$$$. При этом в ответе все подстроки будут перемешаны, а в каждой из подстрок будут перемешаны буквы.
• ! s — сделать предположение о загаданной строке. Этот запрос нужно сделать ровно один раз, после него игра завершается. Если строка угадана, то пациент побеждает, а иначе проигрывает.

Пациенту разрешено сделать не более $$$3$$$ запросов первого типа. Чтобы игра была не так утомительна для санитаров, существует следующее ограничение: суммарно на запросы первого типа должно быть возвращено не более $$$\left\lceil 0.777(n+1)^2 \right\rceil$$$ подстрок ($$$\lceil x \rceil$$$ — округление вверх числа $$$x$$$).

Помогите пациенту выиграть и выбраться из дурдома!

После запроса второго типа ваша программа должна немедленно завершиться. В случае, если ваша программа неверно угадает строку или превысит заданные ограничения на количество запросов или количество возвращенных подстрок, она получит вердикт Неправильный ответ.

Обратите внимание, что в каждом тесте строка фиксирована и не меняется в ходе игры. Иными словами, интерактор не адаптивен.

Вы начинаете своё взаимодействие, считав $$$n$$$.

Для того, чтобы задать вопрос о подстроке с $$$l$$$ по $$$r$$$ включительно ($$$1 \le l \le r \le n$$$) выведите в отдельной строке

? l r

В ответ вы получите все подстроки строки $$$s[l..r]$$$ в случайном порядке, каждую ровно один раз. В каждой из подстрок будут случайным образом перемешаны буквы.

В случае, если вы сделаете некорректный запрос, зададите более $$$3$$$ запросов данного типа, или в результате заданных запросов Вам будет возвращено суммарно более $$$\left\lceil 0.777(n+1)^2 \right\rceil$$$ подстрок, то ваше решение получит вердикт Неправильный ответ.

Для того, чтобы сделать предположение о загаданной строке $$$s$$$ выведите в отдельной строке

! s

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Если вы получили строку - (дефис) в качестве ответа на какой-либо запрос, то вам надо завершить программу штатным образом с кодом возврата 0 (например, сделав exit(0)). Это означает, что интерактор зафиксировал ошибку в протоколе или поведении программы. Если вы не завершите в этом случае программу штатным образом с кодом возврата 0, то можете получить любой неуспешный вердикт.

Формат взломов.

Для взломов используйте следующий формат:

В первой строке должно быть единственное число $$$n$$$ ($$$1 \le n \le 100$$$) — длина загадываемой строки.

Во второй строке выведите строку $$$s$$$ – сама загадываемая строка.