All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

Riyaz & Dhruv
No tags

Riyaz and Dhruv were friends since childhood days. But, as they grew up Dhruv started behaving weird and this used to irritate Riyaz. Once, while Riyaz took a break after typing a large program. Dhruv came from nowhere and swapped some alphabet keys on Riyaz's keyboard.

Riyaz got very angry on seeing this and decided to end their friendship once forever. As we all know Dhruv is very good at heart and never does anything wrong intentionally. He decided to type the remaining program with the same keyboard Configuration. Given the original fragment of the code that Dhruv needs to type, you need to tell Dhruv the code that he should type to get the original code as output.

Help him save his friendship with Riyaz.

Input : 

The first line of the input contains a single integer N denoting the number of swaps done by Dhruv. Next N lines contain a pair of characters A, B denoting the characters which are swapped by Dhruv (Note that Dhruv performs these swaps in the given order). From the very next line of input, the remaining fragment of the code starts and ends with an end of file character.

Output :

print the fragment of the program that Dhruv types.

Constraints :

1 ≤ N ≤ 106

1 ≤ |length of codefragment| <= 106

code fragment contains uppercase and lowercase English alphabets only and space.

A, B belongs to the Alphabet set (both upper case and lower case letters are included).


For the given test case:

Letter W is swapped with the letter H. So, to type WelloHorld Dhruv must type HelloWorld on Riyaz's keyboard.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


Initializing Code Editor...
View All Notifications