← 返回题目列表

AtCoder · abc342_c

E. 许多替换

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

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

您将执行一项操作 Q 次字符串 S。 的 网格的 i第次操作 (1\leq i\leq Q) 由一对字符表示 (c _ i,d _ i),对应如下操作:

  • 替换所有出现的字符 c _ i in S 与字符 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。 例如,在第四个操作中,所有出现的 a in S={}aecovea (第一个和第七个字符)替换为 r,导致 S={}recover.

所有操作完成后, S={}recover,所以打印 recover.


示例输入 2

3
abc
4
a a
s k
n n
z b

示例输出 2

abc

可能存在以下操作 c _ i=d _ i or 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