You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个长度为 $N$、只包含小写字母的字符串 $S$，对其进行 $Q$ 次操作，每次操作记为 $(c_i,d_i)$，表示将当前 $S$ 中所有的字母 $c_i$ 替换成 $d_i$。求经过这 $Q$ 次操作后的 $S$。

数据范围

• $1\le N,Q\le 2\times 10^5$
• $S$ 中的所有字符均为小写字母
• $c_i,d _ i$ 是小写字母 $(1\leq\ i\leq\ Q)$
• $N,Q$ 是整数

输入格式

输入格式如下所示：

$N$

$S$

$Q$

$c _1$ $d_1$

$c_2$ $d_2$

$\vdots$

$c_Q$ $d_Q$

输出格式

$S$ 经过 $Q$ 次操作后得到的字符串。

样例 #1

样例输入 #1

8
zhixinhs
4
z y
s n
h u
i a

样例输出 #1

yuaxanun

样例说明：字符串 $S$ 的变换过程为 zhixinhs $\rightarrow$ yhixinhs $\rightarrow$ yhixinhn $\rightarrow$ yuixinun $\rightarrow$ yuaxanun。

样例 #2

样例输入 #2

3
abc
4
a a
s k
n n
z b

样例输出 #2

abc

样例说明：如本例所示，可能会有 $c_i=d_i$ 的变换，或者 $S$ 中没有 $c_i$ 的变换。

样例 #3

样例输入 #3

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

样例输出 #3

laklimamriiamrmrllrmlrkramrjimrial