1337 - Cryptanalysis

問題

山本くんは厨二病なので、文字列を暗号のように書きます。
山本くんの書いた文字列は以下の操作を順に $N$ 回行うことで解読することができます。

• 文字列中の全ての文字 $A$ を文字 $B$ に変える

山本くんが書いた文字列 $S$ と $N$ 回の操作が与えられるので、解読後の文字列 $S'$ を出力してください。

入力

$S$
$N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

出力

文字列 $S$ を解読したあとの文字列 $S'$ を出力せよ。
出力の最後に改行を入れること。

制約

全ての入力ケースについて以下を満たす。

• $1 \leq |S| \leq 10^5$
• $0 \leq N \leq 10^5$
• $S$ は英大文字で構成される
• $A_i, B_i(1 \leq i \leq N)$ は英大文字である

入出力例

入力例1

GHUKSJ
6
G J
J N
H A
U K
S U
K S

出力例1

NASSUN

解説

操作中の文字列は以下のようになる。
$0$ 回目: GHUKSJ
$1$ 回目: JHUKSJ
$2$ 回目: NHUKSN
$3$ 回目: NAUKSN
$4$ 回目: NAKKSN
$5$ 回目: NAKKUN
$6$ 回目: NASSUN

入力例2

YAMAMOTO
0

出力例2

YAMAMOTO

入力例3

TAKAHASHI
2
S C
S A

出力例3

TAKAHACHI

順に操作を行うことに注意してください。