C1. Дурдом (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

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

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

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

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

Входные данные

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

Протокол взаимодействия

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

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

? l r

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

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

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

Пример
Входные данные
4

a
aa
a

cb
b
c

c
Выходные данные
? 1 2

? 3 4

? 4 4

! aabc