题目描述

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

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

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

输入描述

在一行上输入两个整数$n,m (1 \le n,m \le 2\times 10^5)$，分别表示字符串长度和操作次数;

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

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

若$op = 1$,则$letter1,letter2$为小写字母，且$letter1\le letter2$;+3

若$op = 2$，则$letter1,letter2$为大写字母，且$letter1\le 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$。