Vigenère Cipher Analysis

The Vigenère cipher encrypts a message with a repeating key. Both the plaintext and the key are strings over the uppercase alphabet ${A, B, \ldots, Z}$; map each letter to a number by $A = 0, B = 1, \ldots, Z = 25$. Given a plaintext $P$ and a key $Q$, the ciphertext $C$ has the same length as $P$ and is defined by

$$C_i = (P_i + Q_{i \bmod |Q|}) \bmod 26,$$

read back as a letter, where the key $Q$ is repeated as often as needed to cover the whole message. Decryption reverses this: $P_i = (C_i - Q_{i \bmod |Q|}) \bmod 26$.

A secret organization, the Amateur Codebreakers Movement (ACM), strongly suspects that a gang of bank robbers is about to strike again. Unfortunately, ACM knows neither the name of the target bank nor the exact day and time. ACM can eavesdrop on the messages exchanged between the robbers and their getaway driver, but every message is encrypted with a Vigenère cipher.

Your task is to break the cipher. You are given two words that are very likely to appear in the original plaintext — so-called cribs (such guessed words were crucial, for example, in breaking the famous Enigma machine).

The input contains several test instances. Each instance consists of four lines:

• the first line contains an integer $K$ with $1 \le K \le 100$, the maximum key length to consider;
• the second and third lines contain the cribs $W_1$ and $W_2$, with $1 \le K \le |W_i| \le 100$;
• the fourth line contains the ciphertext $C$, with $1 \le |C| \le 100000$.

Both cribs $W_1, W_2$ and the ciphertext $C$ consist only of uppercase letters of the English alphabet ${A, B, C, \ldots, Z}$. The input ends with a line containing a single $0$.

For each instance, count the distinct plaintexts that satisfy all of the following:

• encrypting the plaintext with some Vigenère key $Q$ whose length satisfies $1 \le |Q| \le K$ yields exactly the given ciphertext $C$;
• the plaintext contains both cribs $W_1$ and $W_2$ at non-overlapping positions — that is, there is an occurrence of $W_1$ and an occurrence of $W_2$ whose ranges of characters are disjoint.

Print one line for each instance:

• if exactly one such plaintext exists, print that plaintext with no extra spaces;
• if two or more such plaintexts exist, print ambiguous;
• if no such plaintext exists, print impossible.