Forgot Password

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef changed the password of his laptop a few days ago, but he can't remember it today. Luckily, he wrote the encrypted password on a piece of paper, along with the rules for decryption.
The encrypted password is a string S consists of ASCII printable characters except space (ASCII 33  126, in decimal notation, the same below). Read here for more details: ASCII printable characters.
Each rule contains a pair of characters c_{i}, p_{i}, denoting that every character c_{i} appears in the encrypted password should be replaced with p_{i}. Notice that it is not allowed to do multiple replacements on a single position, see example case 1 for clarification.
After all the character replacements, the string is guaranteed to be a positive decimal number. The shortest notation of this number is the real password. To get the shortest notation, we should delete all the unnecessary leading and trailing zeros. If the number contains only nonzero fractional part, the integral part should be omitted (the shortest notation of "0.5" is ".5"). If the number contains zero fractional part, the decimal point should be omitted as well (the shortest notation of "5.00" is "5").
Please help Chef to find the real password.
Input
The first line of the input contains an interger T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single interger N, denoting the number of rules.
Each of the next N lines contains two spaceseparated characters c_{i} and p_{i}, denoting a rule.
The next line contains a string S, denoting the encrypted password.
Output
For each test case, output a single line containing the real password.
Constraints
 1 ≤ T ≤ 1000
 0 ≤ N ≤ 94
 All characters in S and c_{i} may be any ASCII printable character except space. (ASCII 33  126)
 All c_{i} in a single test case are distinct.
 p_{i} is a digit ("0"  "9") or a decimal point "." (ASCII 46).
 The total length of S in a single input file will not exceed 10^{6}.
Example
Input: 4 2 5 3 3 1 5 0 01800.00 0 0.00100 3 x 0 d 3 # . 0xd21#dd098x Output: 3 1800 .001 321.33098
Author:  stzgd 
Tester:  shiplu 
Editorial  http://discuss.codechef.com/problems/FORGETPW 
Tags  adhoc, june14, simple, stzgd 
Date Added:  9052014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 