解题思路

• 操作并不是对字符串中的“区间位置”生效，而是对字母表中的一个字母区间生效（如 [a,c]），把所有出现的这些字母统一大小写转换。

• 因此，我们不需要一遍遍扫描字符串；只要记录每个字母最近一次被“转成大写”的操作时间与最近一次被“转成小写”的操作时间即可。

• 设：

  • last_up[c]：字母 c（0~25）最近一次被“转大写”的操作编号（没有则为 0）
  • last_low[c]：字母 c最近一次被“转小写”的操作编号（没有则为 0）

• 读入每个操作 [letter1, letter2]（保证 letter1 <= letter2），把这个闭区间内对应字母的 last_up 或 last_low 更新为该操作的编号 i。

题目内容

小美有一个长度为$n$，仅由大小写英文字母组成的字符串$s$。小美将对字符串执行以下$m$次操作:

• 当操作类型$op=1$且给定两个小写字母$letter1,letter2$(满足$letter1≦letter2$)时，将字符串中所有位于字母表中$[letter1,letter2]$的小写字母转换为对应的大写字母;

• 当操作类型$op=2$且给定两个大写字母$letter1,letter2$(满足$letter1≦letter2$)时，将字符串中所有位于字母表中$[letter1,letter2]$的大写字母转换为对应的小写字母。

输入描述

在一行上输入两个整数$n,m (1 ≦n,m ≦ 2×105)$，分别表示字符串长度和操作次数;

在一行上输入一个长度为$n$，仅由大小写英文字母组成的字符串s;

接下来$m$行，每行输入三个元素:整数$op$和两个字符$letter1,letter2$，满足:

• 若$op = 1$,则$letter1,letter2$为小写字母，且$letter1≦letter2$;
• 若$op = 2$，则$letter1,letter2$为大写字母，且$letter1≦letter2$。

输出描述

输出执行完所有操作后得到的最终字符串。

样例1

输入

3 1
abc
1 a c

输出

ABC

说明

在此样例中，初始字符串"$abc$"，将区间$[a,c]$的小写字母统一转换成大写，得到"$ABC$"。

样例2

输入

6 2
aAbBcC
1 a b
2 B C

输出

AAbbcc

说明

在此样例中，

• 第一次操作将字符串中所有满足字母表区间$[a,b]$所有小写字母的变为大写字母，得到"$AABBcC$";
• 第二次操作将字符串中所有满足字母表区间$[B,C]$所有大写字母的变为小写字母，最终得到"$AAbbcc$"。