Problem Description
A computer scientist has developed an encryption algorithm. This algorithm takes two inputs - one plain word and another, a key. Characteristics of inputs are as below.
Plain word: It is a string consisting of lowercase alphabets only.
Key: It is a set of pairs of strings consisting of lowercase alphabets only. For each pair, first string is the plain word and second string is its secret word. The characters of these secret words are jumbled but lengths of Plain Word and Secret Word are equal.
This algorithm finds the secret characters for each character in the inputted plain word by using the key. Then it combines all the secret characters in the same order to form a string called the secret word. Finally output this secret word. Below table shows how secret characters can be obtained from the key.
Examples
com.tcs.cv.automata.ei.middleware.DocxToHtmlConverter@1acddf9c:image1.png
Your task is to help him in implementing the algorithm as a computer program.
Note: It is guaranteed that all characters in the given plain word can be converted to secret characters by using the given key.
Note: It is guaranteed that one plain text can be converted to only one encrypted text.
Constraints
1 <= P <= 52000
1 <= N <= 26
1 <= Length of a plain word in pair <= 50000
1 <= Length of a secret word in pair <= 50000
Length (plain word) == Length (secret word)
Input
First line contains string P denoting the plain text.
Second line contains an integer N denoting number of key pairs.
Next N lines, each contain two space separated strings denoting plain text and key.
Output
Print the encrypted word.
Time Limit
1
Examples
Example 1
Input
load
3
app lol
old tip
odd itt
Output
piot
Explanation
"load" is the plain word to be encrypted. Given Key contains 3 pairs of Plain word and Secret word combination. They are <"app", "lol">, <"old", "tip"> and <"odd", "itt">. From first pair, it's clear that the secret character of 'p' is 'l' and that of 'a' is 'o'. From third pair, it's clear that the secret character of 'd' is 't' and that of 'o' is 'i'. By using above findings, from second pair, it is clear that the secret character of 'l' is 'p'. Now we can build the secret word by replacing the characters of plain word by its corresponding secret characters as "piot".
Example 2
Input
a
1
a b
Output
b
Explanation
The word "a" is the plain word to be converted to secret word. The given key consists of only one plain word - secret word pair. i.e., <"a", "b">. From this, it is clear that the secret character of 'a' is 'b', since there is only one character in both secret and plain words. So, the final output is "b".
--Comment your solution--
0 Comments