C - Many Replacement Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 350 点

問題文

英小文字からなる長さ 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 と変化します。 たとえば、4 番目の操作では S={}aecovea に含まれる a （1 文字目と 7 文字目）をすべて 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

Score: 350 points

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