URI Online Judge | 2692

Zoeiro Keyboard

By Samuel Lucas Santos Gomes, IFSULDEMINAS BR Brazil

Timelimit: 1

What, ready? Once again we need your help! After a few device exchanges and maintenance in the computer building, the IF keyboards (IFSULDEMINAS) suffered a bad taste in keyboard formatting, their keys are switched. Because the IF computers are prepared to receive any software, develop as quickly as possible a program that converts the sentences correctly.

Note: The keyboard has changed all keys on the keyboard, so all characters are accepted.

Input

It will have two integers N and M indicating respectively: the number of letters that were exchanged, and the phrases that were entered, then E and S, which are the M transformations that occur on the keyboard.

Output

Print the correct sentence as soon as possible.

Input Sample Output Sample

5 3
w l
s m
e o
a b
c z
mbs loww 2017
tozwbde ceoire
ifmuwdosinbm

sam well 2017
teclado zoeiro
ifsuldeminas