Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://cf.m27.workers.dev/blog/entry/45307.
Жюри выбрало строку \(s\) из \(n\) символов; каждый символ \(s\) — это строчная буква латинского алфавита. Ваша задача — угадать эту строку. Изначально вам известна только длина строки.
Вы можете отправлять запросы двух типов:
- \(1\) \(i\) — запрос первого типа, в котором \(i\) — целое число от \(1\) до \(n\). В ответ на такой запрос программа жюри выведет символ \(s_i\);
- \(2\) \(l\) \(r\) — запрос второго типа, в котором \(l\) и \(r\) — целые числа, для которых \(1 \le l \le r \le n\). В ответ на такой запрос программа жюри выведет целое число, равное количеству различных символов среди \(s_l, s_{l+1}, \dots, s_r\).
Вы можете отправить не более \(26\) запросов первого типа и не более \(6000\) запросов второго типа. Ваша задача — восстановить строку \(s\).
В каждом тесте к этой задаче строка \(s\) — фиксированная и не меняется при запуске разных решений на одном и том же тесте. Иными словами, интерактор этой задачи не является адаптивным.
Выходные данные
Чтобы дать ответ на задачу, выведите одну строку ! s с символом перевода строки в конце, где \(s\) — загаданная строка. После этого ваша программа должна сбросить буфер вывода и завершиться.
Протокол взаимодействия
Чтобы отправить запрос, выведите строку, содержащую этот запрос, в одном из следующих форматов:
- ? 1 i — для запроса первого типа (\(1 \le i \le n\));
- ? 2 l r — для запроса второго типа (\(1 \le l \le r \le n\)).
Не забудьте сбросить буфер вывода после того, как выведете строку-запрос.
Ответ на ваш запрос будет выведен на отдельной строке. Для запроса первого типа ответом будет символ \(s_i\). Для запроса второго типа ответом будет целое число, равное количеству различных символов среди \(s_l, s_{l+1}, \dots, s_r\).
Вы можете отправить не более \(26\) запросов первого типа и не более \(6000\) запросов второго типа.
Если вы зададите слишком много запросов, или же программа жюри не сможет распознать формат запроса, ответом на запрос будет число \(0\). После получения ответа \(0\) ваша программа должна сразу же завершиться — иначе вы можете получить вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-то другой вместо вердикта «Неправильный ответ».
Примечание
Давайте разберем пример взаимодействия из условия.
Загаданная строка — guess, поэтому изначально программа жюри выводит одно целое число \(5\).
- первый запрос — ? 2 1 5, что означает «посчитайте количество различных символов среди \(s_1, s_2, \dots, s_5\)». Ответ на этот запрос — \(4\).
- второй запрос — ? 1 2, что означает «выведите символ \(s_2\)». Ответ на этот запрос — u.
- третий запрос — ? 2 1 2, что означает «посчитайте количество различных символов среди \(s_1\) и \(s_2\)». Ответ на этот запрос — \(2\).
- четвертый запрос — ? 1 1, что означает «выведите символ \(s_1\)». Ответ на этот запрос — g.
- пятый запрос — ? 1 3, что означает «выведите символ \(s_3\)». Ответ на этот запрос — e.
- шестой запрос — ? 1 4, что означает «выведите символ \(s_4\)». Ответ на этот запрос — s.
- седьмой запрос — ? 2 4 5, что означает «посчитайте количество различных символов среди \(s_4\) и \(s_5\)». Ответ на этот запрос — \(1\), и можно догадаться, что \(s_4\) и \(s_5\) — одинаковые символы.
В конце ответ на задачу отправляется в формате ! guess, и он является правильным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4
u
2
g
e
s
1
|
? 2 1 5
? 1 2
? 2 1 2
? 1 1
? 1 3
? 1 4
? 2 4 5
! guess
|