Lero-Lero of Mineira
By Lucas Maciel e Guilherme Gomes 
Brazil
By Lucas Maciel e Guilherme Gomes Brazil
At 45 minutes of the second half, a problem had to be solved for the 2018 Programming Mineira Marathon. But it was not any problem, it was that problem. To touch terror in the hearts of competitors. Get the coaches to break their heads in their room trying to solve it. Well, after much work, the Marathon Committee has been able to work out such a problem, and the result is the one you are reading!
Enough of coaxing and let's get down to business. You will receive a list of replacement rules that must be made in a text. Each rule consists of a letter and a corresponding string by which the letter should be replaced. After that, you will receive the string where the rules should be applied. Whenever you find in this string one of the characters that must be replaced according to the rules received, you must replace the character with its corresponding string until it is no longer possible to change the string by making substitutions of this type. If there is always a change to be made, you must advise that it is impossible to end the process.
The entry begins with a line containing an integer N: the number of substitution rules. The following N lines each describe a substitution rule. The i-th of these lines will contain a letter Li, followed by a space and a string Si by which the letter Li must be replaced.
The following line will contain a T number: the size of the text where substitution rules should be applied. The last line will contain a string S with this text.
0 ≤ N ≤ 26
1 ≤ | Si | ≤ 100
1 ≤ T ≤ 105
All input strings will contain only lowercase letters.
There will never be more than one substitution rule for the same letter.
Write in the output a line containing a string that is the result of the successive application of the substitution rules given in the string S, or -1, if the string is changed indefinitely by applying the rules. It is guaranteed that if it is possible to get a string that can no longer be changed by the substitution rules, it will contain a maximum of 5 × 106 letters.
| Input Samples | Output Samples |
|
3 |
dddddddd |
|
3 |
-1 |