6595 - 整串改签

题目描述

科技节布展时,各展台挂着一排字母标签,用一个长度为 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
说明

样例 1 解释

第一次改签后为 CBCCBC,第二次后为 BBBBBB。

样例 2 解释

先得到 BBC,再得到 AAC。后一次改签也会作用于此前由其他字母变来的 B。

样例 3 解释

没有改签记录,输出原串。

数据范围

  • 对于 70\% 的数据,1\le n\le2000,0\le q\le2000。
  • 对于 100\% 的数据,1\le n\le2\times10^5,0\le q\le2\times10^5,|S|=n。
  • 字符串和记录中的字母均为大写英文字母,允许 x=y。
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 10
通过人数 4
金币数量 0 枚
难度 入门


上一题 下一题