Это интерактивная задача!
Это был обычный день в тайном офисе в 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». Эта та строка, которую взламываемому решению придётся угадать.