多次替换

题目描述

给定长度为 $N$、由小写英文字母组成的字符串 $S$。

你将对该字符串 $S$ 执行 $Q$ 次操作。 第 $i$ 次操作 $(1\le i\le Q)$ 由字符对 $(c_i,d_i)$ 表示,对应以下操作：

将 $S$ 中所有 $c_i$ 字符替换为 $d_i$ 字符。

输出所有操作完成后的字符串 $S$。

输入格式

输入按以下格式从标准输入给出：

$N$
$S$
$Q$
$c_1$ $d_1$
$c_2$ $d_2$
$\vdots$
$c_Q$ $d_Q$

输出格式

输出所有操作完成后的字符串 $S$。

样例

7
atcoder
4
r a
t e
d v
a r

recover

$S$ 按如下方式变化:atcoder → atcodea → aecodea → aecovea → recover。 例如,在第 4 次操作中,$S={}$aecovea 中所有 a(第 1 个和第 7 个字符)都被替换为 r,得到 $S={}$recover。

所有操作完成后,$S={}$recover,所以输出 recover。

3
abc
4
a a
s k
n n
z b

abc

可能存在 $c_i=d_i$ 或 $S$ 中不含 $c_i$ 的操作。

34
supercalifragilisticexpialidocious
20
g c
l g
g m
c m
r o
s e
a a
o f
f s
e t
t l
d v
p k
v h
x i
h n
n j
i r
s i
u a

laklimamriiamrmrllrmlrkramrjimrial

数据范围

• $1 \le N \le 2\times 10^5$
• $S$ 是长度为 $N$、由小写英文字母组成的字符串。
• $1 \le Q \le 2\times 10^5$
• $c_i$ 和 $d_i$ 是小写英文字母 $(1\le i\le Q)$。
• $N$ 和 $Q$ 是整数。