103422: [Atcoder]ABC342 C - Many Replacement

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters.

You will perform an operation $Q$ times on the string $S$. The $i$-th operation $(1\leq i\leq Q)$ is represented by a pair of characters $(c _ i,d _ i)$, which corresponds to the following operation:

• Replace all occurrences of the character $c _ i$ in $S$ with the character $d _ i$.

Print the string $S$ after all operations are completed.

Constraints

• $1\leq N\leq2\times10^5$
• $S$ is a string of length $N$ consisting of lowercase English letters.
• $1\leq Q\leq2\times10^5$
• $c _ i$ and $d _ i$ are lowercase English letters $(1\leq i\leq Q)$.
• $N$ and $Q$ are integers.

Input

The input is given from Standard Input in the following format:

$N$
$S$
$Q$
$c _ 1$ $d _ 1$
$c _ 2$ $d _ 2$
$\vdots$
$c _ Q$ $d _ Q$

Output

Print the string $S$ after all operations are completed.

Sample Input 1

7
atcoder
4
r a
t e
d v
a r

Sample Output 1

recover

$S$ changes as follows: atcoder → atcodea → aecodea → aecovea → recover. For example, in the fourth operation, all occurrences of a in $S={}$aecovea (the first and seventh characters) are replaced with r, resulting in $S={}$recover.

After all operations are completed, $S={}$recover, so print recover.

Sample Input 2

3
abc
4
a a
s k
n n
z b

Sample Output 2

abc

There may be operations where $c _ i=d _ i$ or $S$ does not contain $c _ i$.

Sample Input 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

Sample Output 3

laklimamriiamrmrllrmlrkramrjimrial

问题描述

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

你需要对字符串 $S$ 进行 $Q$ 次操作。 第 $i$ 次操作 $(1\leq i\leq Q)$ 由一对字符 $(c _ i,d _ i)$ 表示，具体操作如下：

• 将字符串 $S$ 中所有出现的字符 $c _ i$ 替换为字符 $d _ i$。

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

限制条件

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

输入

输入数据通过标准输入给出，格式如下：

$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

样例输出1

recover

字符串 $S$ 的变化过程如下：atcoder → atcodea → aecodea → aecovea → recover。 以第四个操作为例，将 $S={}$aecovea 中所有出现的字符 a（第一个和第七个字符）替换为 r，得到 $S={}$recover。

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

样例输入2

3
abc
4
a a
s k
n n
z b

样例输出2

abc

可能有 $c _ i=d _ i$ 或者 $S$ 不包含 $c _ i$ 的操作。

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