问题陈述

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

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

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

在所有操作完成后，打印字符串 $S$。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $S$ 是一个长度为 $N$ 的字符串，由小写英文字母组成。
• $1 \leq Q \leq 2 \times 10^5$
• $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$。

样例

7
atcoder
4
r a
t e
d v
a r

recover

字符串替换过程解释

给定初始字符串 ​**S** 为 atcoder，经过多次字符替换操作后最终变为 recover。具体步骤如下：

1. 初始状态

• ​S = atcoder
  （原始字符串）

2. 第一次操作：替换 r → a

• ​操作描述：将字符串末尾的字符 r 替换为 a
  ​替换结果：atcoder → atcodea
  （仅替换最后一个字符）

3. 第二次操作：替换 t → e

• ​操作描述：将第三个字符 t 替换为 e
  ​替换结果：atcodea → aecodea
  （原字符串 a t c o d e a → a e c o d e a）

4. 第三次操作：替换 d → v

• ​操作描述：将第五个字符 d 替换为 v
  ​替换结果：aecodea → aecovea
  （原字符串 a e c o d e a → a e c o v e a）

5. 第四次操作：替换所有 a → r

• ​操作描述：将所有 a 替换为 r
  ​替换结果：aecovea → recover
  • 第一个字符 a → r
  • 第七个字符 a → r
    （原字符串 a e c o v e a → r e c o v e r）

最终结果

所有操作完成后，​S = recover，因此输出 recover。

3
abc
4
a a
s k
n n
z b

abc

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