← 返回题目列表

Codeforces · 591/B

B. 品牌重塑

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

一家小而自豪的公司名称由n个小写英文字母组成。该公司决定尝试品牌重塑——一种积极的营销策略,包括一系列改变品牌(公司及其生产的商品)或其组成部分的措施:名称、徽标、口号。他们决定从名字开始。

为此公司已连续聘请了m名设计师。一旦公司雇用了第 i 个设计师,他立即为创建一个新的公司名称做出贡献,如下所示:他采用该名称的最新版本,并将所有字母 xi 替换为 yi,将所有字母 yi 替换为 xi。这产生了新版本。其中某些字母可能没有出现在字符串中。 xi 也可能与 yi 重合。最后一位设计师工作后收到的名称版本成为公司的新名称。

经理Arkady最近在这家公司找到了一份工作,但他已经沉浸在团队合作的精神中,并且非常担心品牌重塑的成功。自然,他迫不及待地想知道公司的新名称是什么。

满足阿尔卡迪的好奇心并告诉他名字的最终版本。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200 000)——分别是初始名称的长度和雇用的设计师数量。

第二行由n个小写英文字母组成,代表公司原名称。

接下来 m 行包含设计者动作的描述:其中第 i 行包含两个空格分隔的小写英文字母 xi 和 yi。

输出

打印公司的新名称。

示例

输入 #1

6 1
police
p m

输出 #1

molice

输入 #2

11 6
abacabadaba
a b
b c
a d
e g
f a
b b

输出 #2

cdcbcdcfcdc

注意

在第二个样本中,公司名称连续变化如下:

$$babacabadaba \rightarrow babcbadbaba$$$$babcbabdbab \rightarrow cacbcacdcac$$$$cacbcacdcac \rightarrow cdcbcdcacdc$$$$c d c b c d c a c d c \rightarrow c d c b c d c a c d c$$$$cdc \rightarrow cdc$$$$cdc \rightarrow 疾病预防控制中心$$