Description

Countries R and S are at war and have sent spies into each other’s territory. After many hardships, Xiao C (pinyin) from country R, who is undercover in country S, finally figured out the encoding rules of country S’s military cipher:

1. The plaintext to be sent by country S’s military is encrypted and then sent over the network. Both the plaintext and the ciphertext consist only of uppercase letters $\texttt{A}\sim\texttt{Z}$ (no spaces or other characters).
2. For each letter, country S specifies a corresponding cipher letter. Encryption replaces every letter in the plaintext with its corresponding cipher letter.
3. Each letter corresponds to exactly one unique cipher letter, and different letters correspond to different cipher letters. A letter may map to itself.

For example, if the cipher letter for $\tt A$ is $\tt A$, and for $\tt B$ is $\tt C$ (others omitted), then the plaintext $\tt ABA$ is encrypted as $\tt ACA$.

Now Xiao C has, via an inside source, one encrypted message together with its corresponding plaintext. He wants to break the cipher based on this information. His process is: scan the plaintext; for a plaintext letter $x$ (any uppercase letter), find the corresponding letter $y$ at the same position in the ciphertext, and conclude that in the cipher, $y$ is the cipher letter for $x$. Continue until one of the following states occurs:

1. All information has been scanned, and all $26$ letters $\texttt{A}\sim\texttt{Z}$ have appeared in the plaintext and obtained their corresponding cipher letters.
2. All information has been scanned, but there exists at least one letter that does not appear in the plaintext.
3. During scanning, an obvious contradiction or error is found (violating the encoding rules of country S’s cipher).

Example:

If some plaintext $\tt XYZ$ is translated as $\tt ABA$, it violates the rule “different letters correspond to different cipher letters.”

While Xiao C is overwhelmed, the headquarters of country R sends another telegram asking him to translate a newly intercepted encrypted message from country S. Please help Xiao C: deduce the cipher from the known pair, and then use the deduced cipher to translate the encrypted message in the telegram.

Input Format

There are three lines. Each line is a string with length between $1$ and $100$.

• The first line is an encrypted message known to Xiao C.
• The second line is the plaintext corresponding to the first line.
• The third line is the encrypted message that country R’s headquarters asks Xiao C to translate.

The testdata guarantees that all strings consist only of uppercase letters $\texttt{A}\sim\texttt{Z}$, and that the lengths of the first and second lines are equal.

Output Format

Output one line.

If the cipher deduction stops in cases $2$ or $3$, output $\tt Failed$. Otherwise, output the plaintext obtained by translating the encrypted message using the deduced cipher.

AA 
AB 
EOWIE

Failed

QWERTYUIOPLKJHGFDSAZXCVBN 
ABCDEFGHIJKLMNOPQRSTUVWXY 
DSLIEWO

Failed 

MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP
YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL
FLSO 

NOIP

Hint

• Explanation for Sample 1: Letters $\tt A$ and $\tt B$ in the plaintext correspond to the same cipher letter, so output $\tt Failed$.
• Explanation for Sample 2: Letter $\tt Z$ does not appear in the plaintext, so output $\tt Failed$.

NOIP 2009 Senior Problem 1.

Translated by ChatGPT 5