D. Угадай строку
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://codeforces.me/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$$$ — фиксированная и не меняется при запуске разных решений на одном и том же тесте. Иными словами, интерактор этой задачи не является адаптивным.

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

Изначально программа жюри выводит одно целое число $$$n$$$ в отдельной строке — размер строки $$$s$$$ ($$$1 \le n \le 1000$$$).

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

Чтобы дать ответ на задачу, выведите одну строку ! 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$$$ ваша программа должна сразу же завершиться — иначе вы можете получить вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-то другой вместо вердикта «Неправильный ответ».

Пример
Входные данные
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
Примечание

Давайте разберем пример взаимодействия из условия.

Загаданная строка — guess, поэтому изначально программа жюри выводит одно целое число $$$5$$$.

  1. первый запрос — ? 2 1 5, что означает «посчитайте количество различных символов среди $$$s_1, s_2, \dots, s_5$$$». Ответ на этот запрос — $$$4$$$.
  2. второй запрос — ? 1 2, что означает «выведите символ $$$s_2$$$». Ответ на этот запрос — u.
  3. третий запрос — ? 2 1 2, что означает «посчитайте количество различных символов среди $$$s_1$$$ и $$$s_2$$$». Ответ на этот запрос — $$$2$$$.
  4. четвертый запрос — ? 1 1, что означает «выведите символ $$$s_1$$$». Ответ на этот запрос — g.
  5. пятый запрос — ? 1 3, что означает «выведите символ $$$s_3$$$». Ответ на этот запрос — e.
  6. шестой запрос — ? 1 4, что означает «выведите символ $$$s_4$$$». Ответ на этот запрос — s.
  7. седьмой запрос — ? 2 4 5, что означает «посчитайте количество различных символов среди $$$s_4$$$ и $$$s_5$$$». Ответ на этот запрос — $$$1$$$, и можно догадаться, что $$$s_4$$$ и $$$s_5$$$ — одинаковые символы.

В конце ответ на задачу отправляется в формате ! guess, и он является правильным.