E. string
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today, DLee is preparing for '17th-bitcpc-online', and he is assigned to set a problem about string.

He thinks a while a write down this description.

DLee has a string $$$S$$$ of length $$$n$$$, which is composed of visible characters (that means each character has ACSII between 33 and 126, without blank space). Now he will do $$$m$$$ operations in order, the $$$i$$$-th operation can be described as $$$(x_i,y_i)$$$, where $$$x_i$$$ and $$$y_i$$$ are two different visible characters. DLee will 'swap' all these two kinds of characters and get a new string, and then continue with the next operation.

A 'swap' of characters $$$x$$$ and $$$y$$$ for string $$$S$$$ means that replace all characters $$$x$$$ with $$$y$$$ and replace all characters $$$y$$$ in $$$S$$$ with $$$x$$$ at the same time.

For example, the initial string $$$S$$$ is '$$$abcd$$$'(without quotation marks), the first operation is ($$$a,c$$$), and the second operation is ($$$z,d$$$). The string $$$S$$$ will first become to '$$$cbad$$$' after the first operation, and then become to '$$$cbaz$$$' after the second operation.

Now DLee want to know the final string after these $$$n$$$ operations.

Input

The first line contains two integers $$$n,m(1\leq n,m\leq 10^5)$$$ — the length of string $$$S$$$ and the number of operations.

The second line contains only one string $$$S$$$ with length $$$n$$$.

The $$$i$$$-th of the next $$$m$$$ lines contains two visible characters $$$x_i,y_i$$$ — the $$$i$$$-th operation is $$$(x_i,y_i)$$$.

Output

Print a single line with the final string after $$$m$$$ operations.

Examples
Input
4 2
abcd
a c
d z
Output
cbaz
Input
5 3
@#$%@
# !
@ !
? !
Output
?@$%?
Note

Each visible character can be store as a 'char'.

In the second example, the string will be changed like '@#$%@'$$$\rightarrow$$$ '@!$%@' $$$\rightarrow$$$ '!@$%!' $$$\rightarrow$$$ '?@$%?'