题目描述

小红拿到了一些有趣的游戏币。

游戏币正面是大写字母，反面是对应的小写字母。现在小红把这些硬币一字排开，得到了一个字符串。

小红每次都会对一个区间[$l$，$r$]内出现次数最多的硬币进行大小写翻转(正面朝上和反面朝上的同一种硬币视为不同的硬币)， 如果有多种不同的硬币出现次数都最多， 小红会把这些硬币全部翻转。

小红希望你在每次操作后输出那时的字符串，请写个程序解决这个问题。

输入描述

输入第一行两个正整数 $n$ , $q$ ,代表硬币个数以及操作次数。($1≤n,q≤1000$)

输入第二行一个长度为 $n$ 的、仅包含大小写字母的字符串表示小红排开的硬币状态。

接下来的 $q$ 行， 每行输入两个正整数$l$，$r$，代表一次操作的区间。($1≤l≤r≤n$)

输出描述

输出 $q$ 行， 每行输出一个字符串， 代表这次操作后的硬币状态。

样例

样例输入

5 3
ACMac
1 3
1 5
2 4

样例输出

acmac
ACmAC
AcMaC