科技节布展时,各展台挂着一排字母标签,用一个长度为 n 的大写字母串 S 表示。布展过程中,工作人员依次执行 q 条改签记录。
每条记录给出两个大写字母 x,y,表示把当前整串中所有字母 x 改成 y。
每条记录只执行一次这样的替换,所有记录都作用于整串,串的长度不变。后面的记录根据前面记录执行后的结果继续修改。
请输出全部记录执行后的字符串。
第一行输入两个整数 n,q。
第二行输入字符串 S。
接下来 q 行,每行输入两个大写字母 x,y,表示一条改签记录。
输出一行,为全部改签记录执行后的字符串。
6 2 ABACBA A C C B
BBBBBB
3 2 ABC A B B A
AAC
4 0 ZAZA
ZAZA
第一次改签后为 CBCCBC,第二次后为 BBBBBB。
先得到 BBC,再得到 AAC。后一次改签也会作用于此前由其他字母变来的 B。
没有改签记录,输出原串。