题目描述

强哥收到了一个神秘的加密字符串 $S$，字符串的长度为 $n$。同时，他还收到了 $q$ 次操作指令，每次操作指令用一对小写字母 $(a,b)$ 表示。操作每次时，强哥需要将目前字符串 $S$ 中所有的字母 $a$ 替换成字母 $b$。经过这 $q$ 次操作后，字符串 $S$ 将被解密成最终的消息。

请帮助强哥计算并输出经过这 $q$ 次操作后的字符串 $S$。

注意：每次操作都是基于当前字符串的状态进行替换，即前一次操作后的结果会影响后续的操作。例如，如果第一次操作将所有的 'a' 替换成 'b'，那么第二次操作如果再将所有的 'b' 替换成 'c'，那么原来的所有 'a' 最终都会变成 'c'。

数据范围：

$1≤n,q≤2*10^5$，保证 $S$ 中的所有字符均为小写字母。

输入格式

第一行包含一个整数和一个字符串 $n,S$ 。

第二行包含一个整数 $q$，表示操作次数

接下来 $q$ 行，每行包含两个小写字母 $a$ 和 $b$，表示一次替换操作。

输出格式

输出一个字符串，表示经过所有 $q$ 操作后的字符串 $S$。

6 abcxab
5
c x
a c
x y
y z
z a

cbaacb

提示