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