Hide

Problem A
Substitution Mania!

/problems/substitutionmania/file/statement/en/img-0001.jpg
Source: pixabay

Your friend Ben absolutely loves substitution ciphers!

A substitution cipher takes the alphabet and lines up a substitution with it, as shown in the example below:

\includegraphics[width=0.35\textwidth ]{SubstitutionMania.jpg}

Then, for each letter of the plaintext, we find that letter in the top row and substitute it with the corresponding letter in the bottom row. The cipher is referred to by the string in the bottom row. In this example, “hello abc” would encrypt to “kpxxt sau” (Ben leaves spaces as spaces so things don’t get too confusing).

Ben always encrypts his messages to you using between $1$ and $12$ substitution ciphers which he applies consecutively because he doesn’t want anyone else getting into your business.

He also gives you the substitution ciphers he uses, but to increase security he doesn’t give them to you at the same time. Unfortunately, sometimes he ends up giving them to you in the wrong order!

Luckily, you have the plaintext and ciphertext of another message that used exactly the same sequence of ciphers. Given this message and the list of ciphers, write a program to decrypt Ben’s latest message!

Input

The first line contains $d_0$, the plaintext of the message you have, with $|d_0| \leq 10\, 000$ where $|d_0|$ denotes the length of the message. The second line contains $e_0$, the ciphertext that corresponds to $d_0$.

The third line contains an integer $1 \leq i \leq 12$, the number of substitution ciphers Ben used.

The following $i$ lines each contain one of the substitution ciphers, each of which is a nonrepeating string of exactly $26$ lowercase letters.

The last line contains $e_1$, the ciphertext of the message you should decrypt.

All lines containing text consist of only lowercase English letters and spaces, with no more than $1$ space separating each word.

You are guaranteed that there is a unique sequence of applications of the given substitution ciphers that encrypts $d_0$ to $e_0$ in which each of the given ciphers is used exactly once.

Output

Output the plaintext $d_1$ obtained after decrypting the ciphertext $e_1$ on a single line.

Sample Input 1 Sample Output 1
hey check out this cool substitution cipher
kpq ukpuz tey ykjn uttx neanyjyeyjti ujfkpv
1
saucpwhkjdzxgitfmvnyeborql
fxpsnp vpnftic
please respond
Sample Input 2 Sample Output 2
hey its your friend ben
lik grp kfnm zmgiyj ciy
5
orcfnushpmbyxzjltdviqgaewk
cwnuayzsqekgltdprovmbhxfji
yfizduprnchxkbvalgwmejoqst
aoxenqjzclgwkytrpdbmuvihfs
tyjgklxocquemhanirdwszvpbf
thy kfn mihj rlgp
can you read this

Please log in to submit a solution to this problem

Log in