一家小而自豪的公司名称由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 疾病预防控制中心$$