该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc342_c [ABC342C] Many Replacement

题目描述

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

你需要对字符串 $S$ 进行 $Q$ 次操作。第 $i$ 次操作 $(1\leq i\leq 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$。

样例 1

输入

7
atcoder
4
r a
t e
d v
a r

输出

recover

样例 2

输入

3
abc
4
a a
s k
n n
z b

输出

abc

样例 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

输出

laklimamriiamrmrllrmlrkramrjimrial

说明/提示

限制条件

• $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$ 均为整数。

样例解释 1

$S$ 依次变化为 atcoder → atcodea → aecodea → aecovea → recover。例如，在第 4 次操作时，$S=$aecovea，将其中的 a（第 1 个和第 7 个字符）全部替换为 r，因此 $S=$recover。所有操作完成后，$S=$recover，因此输出 recover。

样例解释 2

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

由 ChatGPT 4.1 翻译