Схований код
Настав час перевірити Ваші хакерські здібності! У Вас попросили допомоги зламати коди ворога в поточній війні з ... або кимось іншим. У всякому разі, Вам слід розкрити техніку шифрування, використовувану супротивником. Це досить просто, і відбувається наступним чином. Відзначимо, що всі рядки містять тільки великі літери латинського алфавіту.
Є ключ 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", якщо такого ключа не існує.