Задачи
Спрятанный код
Спрятанный код
Пришло время проверить Ваши хакерские способности! У Вас попросили помощи взломать коды врага в текущей войне с ... или кем-то другим. Во всяком случае, Вам следует раскрыть технику шифрования, используемую противником. Это достаточно просто, и происходит следующим образом. Отметим, что все строки содержат только заглавные буквы латинского алфавита.
\begin{enumerate}
\item Имеется ключ \textbf{K} и открытый текст \textbf{P}. Он закодирован посимвольно, в результате чего получен шифр \textbf{C} такой же длины.
\item Обозначим через |\textbf{K}| длину ключа \textbf{K}. Тогда первые |\textbf{K}| символов \textbf{C} получены добавлением первых |\textbf{K}| символов \textbf{P} к символам \textbf{K}. Под добавлением двух символов имеется в виду их интерпретация как чисел (\textbf{A = 0}, \textbf{B = 1} и так далее) и взятие суммы по модулю \textbf{26}. То есть \textbf{C_i = (P_i + K_i ) mod 26} для \textbf{i = 1, ... ,|K|}. Если |\textbf{K}| > |\textbf{P}|, то лишние символы \textbf{K} игнорируются.
\item Оставшиеся символы \textbf{P}, то есть \textbf{P_i} для \textbf{i} > |\textbf{K}|, кодируются с использованием предыдущих символов шифротекста по формуле \textbf{C_i = (P_i + C_\{i−|K|\}) mod 26} для \textbf{i = |K| + 1, ..., |P|}.
\end{enumerate}
Например, рассмотрим шифрование строки "\textbf{STANFORD}" ключом "\textbf{ACM}":
\textbf{STA NFORD + ACM SVMFA ---------- SVM FAAWD}
Зная алгоритм, Вам необходимо прочесть сообщения врага. К счастью, у Вас имеются несколько открытых текстов и соответствующих им шифротекстов, добытых Вашей командой. Известно, что все они зашифрованы одним и тем же ключом. Помогите найти ключ, которым пользовался противник.
\InputFile
Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей количество \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{100}) известных Вам пар текст - шифротекст. Каждая из \textbf{n} следующих строк содержит две строки \textbf{P} и \textbf{C} - текст и шифротекст соответственно. \textbf{P} и \textbf{C} содержат только заглавные буквы (\textbf{A}-\textbf{Z}) и имеют одинаковую длину (не более \textbf{100} символов). Последняя строка содержит \textbf{n = 0} и не обрабатывается.
\OutputFile
Для каждого теста в отдельной строке вывести кратчайший возможный ключ, или "\textbf{Impossible}", если такого ключа не существует.
Входные данные #1
1 A B 3 STANFORD SVMFAAWD AVOWIENR AXAWFEJW VAMRI VCYMK 3 ABCDEFGHIJKLMNOPQRSTUVWXYZ AAAAAAAAAAAAAAAAAAAAAAAAAA Y Y Z Z 2 A B B A 0
Выходные данные #1
B ACM AZYXWVUTSRQPONMLKJIHGFEDCB Impossible