E. Рин и неизвестный цветок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Это был обычный день в тайном офисе в A.R.C. Markland-N, когда капитан-исследователь Сагар передал Рин необычный артефакт.

После некоторого анализа, Рин поняла, что этот артефакт содержит информацию о странном цветке, который существовал задолго до нашей эры. Однако информация о химической структуре цветка оказалась зашифрованной.

Химическая структура цветка может быть представлена как строка $$$p$$$. Исходя из незашифрованных бумаг рядом, Рин выяснила, длину строки $$$n$$$ и что эта строка может содержать только следующие три буквы: «C» (углерод), «H» (водород), и «O» (кислород).

В каждый момент Рин может ввести строку $$$s$$$ произвольной длины в специальный терминал артефакт, и он в ответ выведет все возможные начальные позиции вхождения $$$s$$$ как подстроки в $$$p$$$.

Тем не менее, запас энергии артефакта достаточно ограничен, и артефакт нельзя перезарядить, так как его технология слишком несовременная и несовместима ни с одним устройством A.R.C. Более точно:

  • Артефакт содержит $$$\frac{7}{5}$$$ единиц энергии.
  • Каждый раз, когда Рин вводит строку $$$s$$$ длины $$$t$$$, артефакт тратит $$$\frac{1}{t^2}$$$ единиц энергии.
  • Если уровень энергии достигнет нуля, то задание будет считаться проваленным, а артефакт навсегда затемнится.

Артефакт очень ценен, но и столь же хрупок. Рин очень боится повредить артефакт навсегда в попытках извлечь данные. Не могли бы вы ей помочь?

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

Взаимодействие начинается с целого числа $$$t$$$ ($$$1 \le t \le 500$$$), количества тестовых случаев. Взаимодействие для каждого тестового случая описано ниже:

Сначала вам нужно считать целое число $$$n$$$ ($$$4 \le n \le 50$$$), длину строки $$$p$$$.

После этого вы можете делать запросы вида «? s» ($$$1 \le |s| \le n$$$), чтобы найти вхождения $$$s$$$ в $$$p$$$.

После запроса, вам нужно считать ответ на него как последовательность целых чисел в одной строке:

  • Первое число $$$k$$$ обозначает количество вхождений $$$s$$$ как подстроку в $$$p$$$ ($$$-1 \le k \le n$$$). Если $$$k = -1$$$, то это означает, что вы превысили ограничение на энергию или сделали некорректный запрос, в этом случае вам нужно немедленно завершить программу, чтобы гарантировать вердикт «Неправильный ответ». В противном случае вердикт может оказаться любым, так как ваше решение продолжит чтение из закрытого потока.
  • Следующие $$$k$$$ целых чисел $$$a_1, a_2, \ldots, a_k$$$ ($$$1 \le a_1 < a_2 < \ldots < a_k \le n$$$) обозначают начальные позиции подстрок равных строке $$$s$$$ .

Когда вы выясните строку $$$p$$$ выведите «! $$$p$$$» чтобы завершить текущий тестовый случай. Это действие не тратит энергию. Интерактор в ответ вернёт $$$1$$$ или $$$0$$$. Если интерактор вернул $$$1$$$, то вы можете начать обрабатывать следующий тестовый случай, если он есть, или завершить программу, если это был последний тестовый случай.

Если интерактор вернул $$$0$$$, то это означает что ваше предположение некорректно и вы должны немедленно завершить программу, чтобы гарантировать вердикт «Неправильный ответ».

Обратите внимание что в каждом тестовом случае строка $$$p$$$ зафиксирована заранее и не меняется в зависимости от запросов, иначе говоря, интерактор не адаптивен.

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

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

Взломы

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

Первая строка должна содержать целое число $$$t$$$ ($$$t = 1$$$).

Вторая строка строка должна содержит целое число $$$n$$$ ($$$4 \le n \le 50$$$) — длину строки.

Вторая строка должна содержать строку длины $$$n$$$, состоящую только из символов «C», «H» и «O». Эта та строка, которую взламываемому решению придётся угадать.

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

2 1 2

1 2

0

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


? C

? CH

? CCHO

! CCHH

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

0

2 2 3

1
8

1 5

1 5

1 3

2 1 2

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


? O

? HHH

! CHHHH


? COO

? COOH

? HCCOO

? HH

! HHHCCOOH

Примечание

Обратите внимание что в примере взаимодействия есть лишние пустые строки для удобства чтения.

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