Схований код#3382

Схований код

1 секунда

64 мегабайти

Середня

Настав час перевірити ваші хакерські здібності! Вас просять допомогти зламати коди ворога у сучасній війні... Як би там не було, ви розкрили техніку шифрування, яку використовує ворог — вона досить проста і працює наступним чином. Зауважте, що всі рядки складаються лише з великих літер латиниці.

Вам задано ключ K та відкритий текст P. Повідомлення P шифрується посимвольно, в результаті чого виходить шифротекст C тієї ж довжини.
Нехай $∣ K ∣$ — довжина ключа K. Перші $∣ K ∣$ символів C отримують шляхом додавання перших $∣ K ∣$ символів P до відповідних символів K. Додавання двох літер означає інтерпретацію їх як числа (A = 0, B = 1, ..., Z = 25) і обчислення суми за модулем $26$ . Тобто $C_{i} = (P_{i} + K_{i}) mod 26$ C_i = (P_i + K_i) \bmod 26 для $i = 1, \dots, ∣ K ∣$ i = 1, \ldots, |K|. Якщо $∣ K ∣ > ∣ P ∣$ |K| > |P|, зайві символи у K ігноруються.
Решта символів P (тобто $P_{i}$ P_i для $i > ∣ K ∣$ i > |K|) шифруються, використовуючи попередні символи шифротексту: $C_{i} = (P_{i} + C_{i - ∣ K ∣}) mod 26$ C_i = (P_i + C_{i - |K|}) \bmod 26 для $i = ∣ K ∣ + 1, \dots, ∣ P ∣$ i = |K| + 1, \ldots, |P|.

Для прикладу, розглянемо шифрування рядка "STANFORD" ключем "ACM":

    STA NFORD
  + ACM SVMFA
  ----------
    SVM FAAWD

Знаючи це, ви майже готові читати повідомлення ворога! На щастя, у вас є декілька пар відкритих текстів і відповідних їм шифротекстів, зашифрованих тим самим ключем. Ваше завдання — знайти ключ, яким користується ворог.

Вхідні дані

Вхідні дані складаються з кількох тестів. Кожен тест починається з одного рядка, що містить одне ціле число $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100) — кількість відомих пар текст-шифротекст. Далі йдуть $n$ рядків, кожен з яких містить два рядки: P (текст) і C (шифротекст). P та C містять лише великі латинські літери (A-Z) і мають однакову довжину (не більше $100$ символів). Останній рядок містить $n = 0$ n = 0 і не обробляється.

Вихідні дані

Для кожного тесту в окремому рядку виведіть найкоротший можливий ключ або Impossible, якщо такого ключа не існує.

Приклади

Приклад 1