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$。

7
atcoder
4
r a
t e
d v
a r

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

提示

$1\leq N\leq2\times10^5$ $S$ 是一个长度为 $N$ 的由小写英文字母组成的字符串。 $1\leq Q\leq2\times10^5$ $c _ i$ 和 $d _ i$ 是小写英文字母 $(1\leq i\leq Q)$。 $N$ 和 $Q$ 是整数。$S$ 的变化如下： $atcoder$ → $atcodea$ → $aecodea$ → $aecovea$ → $recover$。 例如，在第四次操作中，$S={}$$aecovea$ 中的所有 $a$（第 1 个和第 7 个字符）都被替换为 $r$，得到 $S={}$$recover$。 在所有操作完成后，$S={}$$recover$，因此输出 $recover$。
可能存在 $c _ i=d _ i$ 的操作，或 $S$ 中不包含 $c _ i$ 的情况。

标签: AtCoder|abc342C

来源

AtCoder|abc342C