Hidden Code#3382

Hidden Code

1 second

64 megabytes

Medium

It's time to put your hacking skills to the test! You've been called upon to help crack enemy codes in the current war on... something or another. Anyway, the point is that you have discovered the encryption technique used by the enemy—it is quite simple, and works as follows. Note that all strings contain only uppercase letters of the English alphabet.

You are given a key K and a plaintext P. The message P is encrypted character-by-character to produce a ciphertext C of the same length.
Let $∣ K ∣$ be the length of the key K. The first $∣ K ∣$ characters of C are obtained by adding the first $∣ K ∣$ characters of P to the corresponding characters of K. Adding two letters means interpreting them as numbers (A = 0, B = 1, ..., Z = 25) and taking the sum modulo $26$ . That is, $C_{i} = (P_{i} + K_{i}) mod 26$ C_i = (P_i + K_i) \bmod 26 for $i = 1, \dots, ∣ K ∣$ i = 1, \ldots, |K|. If $∣ K ∣ > ∣ P ∣$ |K| > |P|, the extra characters in K are ignored.
The remaining characters of P (i.e., $P_{i}$ P_i for $i > ∣ K ∣$ i > |K|) are encrypted using the previous ciphertext characters: $C_{i} = (P_{i} + C_{i - ∣ K ∣}) mod 26$ C_i = (P_i + C_{i - |K|}) \bmod 26 for $i = ∣ K ∣ + 1, \dots, ∣ P ∣$ i = |K| + 1, \ldots, |P|.

As an example, consider encrypting the string "STANFORD" using the key "ACM":

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

With this information, you are well on your way to reading the enemy's messages! Fortunately, you also have several pairs of corresponding plaintexts and ciphertexts, all encrypted with the same secret key. Your mission is to find the key that the enemy is using.

Input

The input consists of multiple test cases. Each test case starts with a line containing a single integer $n$ ( $1 \leq n \leq 100$ 1 \leq n \leq 100), the number of plaintext and ciphertext pairs. The next $n$ lines each contain two strings: P (plaintext) and C (ciphertext). Both P and C contain only uppercase letters (A-Z) and are of the same length (no more than $100$ characters). The input ends with a line containing $n = 0$ n = 0.

Output

For each test case, output a single line containing the shortest possible key, or Impossible if no possible key could have produced all the encryptions.

Examples

Example 1