Эта задача отличается от сложной версии только ограничением на суммарную длину ответов
Это интерактивная задача.
Веня приехал на экскурсию в дурдом, в котором санитары играют с пациентами в следующую игру: санитары загадывают строку \(s\) длины \(n\), состоящую только из строчных букв английского алфавита. Пациент может делать запросы двух типов:
- ? l r — запросить все подстроки \(s[l..r]\). При этом в ответе все подстроки будут перемешаны, а в каждой из подстрок будут перемешаны буквы.
- ! s — сделать предположение о загаданной строке. Этот запрос нужно сделать ровно один раз, после него игра завершается. Если строка угадана, то пациент побеждает, а иначе проигрывает.
Пациенту разрешено сделать не более \(3\) запросов первого типа. Чтобы игра была не так утомительна для санитаров, существует следующее ограничение: суммарно на запросы первого типа должно быть возвращено не более \((n+1)^2\) подстрок.
Помогите пациенту выиграть и выбраться из дурдома!
После запроса второго типа ваша программа должна немедленно завершиться. В случае, если ваша программа неверно угадает строку или превысит заданные ограничения на количество запросов или количество возвращенных подстрок, она получит вердикт Неправильный ответ.
Обратите внимание, что в каждом тесте строка фиксирована и не меняется в ходе игры. Иными словами, интерактор не адаптивен.
Протокол взаимодействия
Вы начинаете своё взаимодействие, считав \(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\) — сама загадываемая строка.