一个名叫 Leo 的男孩不会错过任何一轮 TorCoder 比赛。在 TorCoder 的最后一轮第 100666 轮中,Leo 偶然发现了以下问题。给他一个字符串 s,由 n 个小写英文字母和 m 个查询组成。每个查询由一对整数 li, ri (1 ≤ li ≤ ri ≤ n) 表征。
我们将从左到右考虑字符串中编号为 1 到 n 的字母,即 s = s1s2... sn。
在每次查询之后,他必须将字符串 s 中从 li 到 ri 的索引与索引交换字母,以使子字符串 (li, ri) 成为回文。如果有多个这样的字母排列,您应该选择字符串 (li, ri) 按字典顺序最小的一个。如果不存在这样的排列,则应忽略该查询(即不更改 string s)。
大家都知道,TorCoder 上的舍入输入行和数组大小限制永远不会超过 60,所以 Leo 轻松解决了这个问题。你的任务是在更大的限制下解决问题。给定字符串 s 和 m 查询,打印将所有 m 查询应用于字符串 s 后得到的字符串。
输入
第一个输入行包含两个整数 n 和 m (1 ≤ n, m ≤ 105) — 字符串长度和查询数量。
第二行包含字符串 s,由 n 个小写拉丁字母组成。
接下来的 m 行中的每一行都包含一对整数 li, ri (1 ≤ li ≤ ri ≤ n) — 应用于字符串的查询。
输出
在一行中打印对字符串 s 应用 m 个查询的结果。按照输入中给出的顺序打印查询。
示例
输入 #1
7 2 aabcbaa 1 3 5 7
输出 #1
abacaba
输入 #2
3 2 abc 1 2 2 3
输出 #2
abc
注意
长度为 n 的字符串 s = s1s2... sn 的子字符串 (li, ri) 1 ≤ li ≤ ri ≤ n) 是字符序列 slisli + 1...sri。
如果一个字符串从左到右和从右到左读起来相同,那么它就是回文。
字符串 x1x2... xp 按字典顺序小于字符串 y1y2... yq,如果 p < q 且 x1 = y1, x2 = y2, ... , xp = yp,或存在这样的数字 r (r < p, r < q),即 x1 = y1, x2 = y2, ... , xr = yr 且 xr + 1 < yr + 1.