Расшифровка кода
Террористическая организация, известная как NewWorld Ensemble for Rebellious Coders (NWERC), представляет угрозу для нашего общества. К счастью, мы нашли способ перехватывать их сообщения, не давая им об этом знать. Однако их сообщения зашифрованы, и это создает проблему.
Известно, что их сообщения состоят только из строчных букв, и метод шифрования - это Базовый Алфавитный Код Перестановки (BAPC). В этом коде каждая одинаковая буква заменяется другой (строчной) буквой из алфавита (или, возможно, той же самой буквой). Очевидно, что две разные буквы в оригинальном сообщении остаются разными после шифрования, так что существует уникальная дешифровка. Например, "hello" может быть зашифровано как "ifmmp" или "holle", но не как "cnoiz" или "bgrrb".
Тем не менее, это оставляет много возможностей, и наши усилия по взлому кода пока были тщетными. К счастью, нам повезло: через информатора мы смогли получить расшифрованное сообщение D. У нас нет соответствующего зашифрованного сообщения, но мы почти уверены, что оно должно быть где-то в списке перехваченных зашифрованных сообщений, которые у нас есть.
Ваша задача - написать программу, которая, получив оригинальное сообщение D и список зашифрованных сообщений, определяет, какая зашифрованная буква соответствует какой расшифрованной букве (предполагая, что одно из зашифрованных сообщений соответствует оригинальному сообщению), насколько это возможно.
Это затем должно быть использовано для дешифровки недавно перехваченного закодированного сообщения X, насколько это возможно. В частности, каждая буква из X, для которой можно с абсолютной уверенностью определить, что она представляет - либо напрямую, либо дедуктивно - должна быть дешифрована. Все остальные буквы должны быть заменены на вопросительный знак.
Обратите внимание, что даже если несколько сообщений могут соответствовать D, все равно может быть возможно дешифровать определенные буквы (см., например, третий тестовый случай в примере ввода).
Входные данные
На первой строке указано одно положительное число: количество тестов, не более 100. После этого для каждого теста:
одна строка с одним целым числом n (1 ≤ n ≤ 100): количество зашифрованных сообщений.
n строк, каждая из которых содержит одно зашифрованное сообщение M_i.
одна строка с расшифрованным сообщением D, предположительно соответствующим одному из зашифрованных сообщений.
одна строка с сообщением X, которое нужно декодировать.
Все строки состоят как минимум из 1 и не более чем из 1000 строчных букв.
Выходные данные
Для каждого теста:
одна строка с результатом Y. Для каждой буквы в X соответствующая буква в Y должна быть расшифрованным аналогом или '?', если она неизвестна. Если нет зашифрованного сообщения M_i, которое могло бы быть зашифрованной версией D, то строка должна быть "IMPOSSIBLE".