Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://cf.m27.workers.dev/blog/entry/45307.
Вам дана строка \(t\), состоящая из \(n\) строчных латинских букв. Эта строка была получена следующим образом: сначала у жюри была строка \(s\), состоящая также из \(n\) строчных латинских букв. Затем к ней применили не более \(n\) (возможно, ни одной) операций. \(i\)-я операция обозначается двумя целыми числами \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le n\)), и означает обмен символов строки под номерами \(a_i\) и \(b_i\). Все операции были выполнены в том порядке, в котором они расположены в последовательности. Например, если \(s\) — xyz, и было выполнено \(2\) операции: \(a_1 = 1, b_1 = 2\); \(a_2 = 2, b_2 = 3\), то после первой операции текущая строка будет yxz, после второй — yzx, поэтому \(t\) — yzx.
Ваше задание — восстановить исходную строку \(s\). К сожалению, о последовательности операций вы ничего не знаете (вы даже не знаете, была ли в ней хотя бы одна операция). Но вы можете использовать ту же самую последовательность обменов на любой строке, на которой вы хотите, если в этой строке ровно \(n\) символов, и все они — строчные латинские буквы. После применения последовательности операций на строке вы можете узнать, во что она превратилась.
Можете ли вы восстановить исходную строку \(s\), использовав последовательность операций не более \(3\) раз?
Строка \(s\) и последовательность операций в каждом тесте являются фиксированными; интерактор не пытается адаптировать тест под ваше решение.
Выходные данные
Чтобы дать ответ, ваша программа должна вывести одну строку \(!\) \(s\) с переводом строки в конце. После этого программа должна сбросить буфер вывода и завершиться.
Протокол взаимодействия
До того, как ваша программа даст ответ, она может отправить не более \(3\) запросов. Чтобы отправить запрос, выведите строку следующего формата: \(?\) \(s'\), где \(s'\) должна быть строкой из ровно \(n\) строчных латинских букв. Строка, которую вы отправляете, должна заканчиваться символов перевода строки. После отправки запроса программа должна сбросить буфер вывода и прочитать ответ на запрос — строку \(t'\), состоящую из \(n\) строчных латинских букв, которая будет являться результатом применения последовательности обменов к \(s'\). Ответ будет дан на отдельной строке, заканчивающейся символом перевода строки.
Если вы зададите некорректный запрос (или же количество запросов превысит \(3\)), ответом будет строка 0. Если ваша программа получила такой ответ, она должна немедленно завершиться — иначе вы можете получить вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-нибудь другой, а не «Неправильный ответ».
Примечание
В примере рассматривается тест, который приводился в условии. Участник задает запрос со строкой baa, которая превращается в aab. Во втором запросе задается строка aba, которая превращается в baa. В третьем запросе задается строка aab, которая превращается в aba. Участник может понять, что изначально строка \(s\) была xyz.
Замечание к фазе взломов:
Чтобы отправить тест в фазу взломов, предоставьте его в следующем виде:
В первой строке должна быть записана строка \(s\), которую вы загадываете, состоящая из \(n \in [1, 10000]\) строчных латинских букв.
Во второй строке должно быть записано одно целое число \(k\) (\(0 \le k \le n\)) — количество операций в последовательности обменов.
Затем должны следовать \(k\) строк, \(i\)-я из которых должна задавать \(i\)-ю операцию обмена двумя целыми числами \(a_i\) и \(b_i\) (\(1 \le a_i, b_i \le n\)).
Например, тест из условия выглядел бы вот так:
xyz
2
1 2
2 3
Примеры
| № | Входные данные | Выходные данные |
|
1
|
yzx
aab
baa
aba
|
? baa
? aba
? aab
! xyz
|