题目内容

塔子哥收到了一封神秘的信件，里面包含了一串长度为 $n$ 的字符串。他注意到这个字符串非常特殊，其中每个字母都可以被重复任意次数。他很好奇，如果把这个字符串的某个子区间重复一遍，会不会得到一个更长的字符串呢？

于是塔子哥开始进行操作，他每次会选择一个区间 $[l,r]$，将第 $l$ 个字母到第 $r$ 个字母各重复一次，并插入到该字母的后面。例如，对于字符串 "abcd"，若选择区间 $[2,3]$ 进行操作，字符串将变成 "abbccd"。

塔子哥一共进行了 $q$ 次操作，他问你在 $q$ 次操作结束后，最终的字符串是什么样子？

输入描述

第一行输入两个正整数 $n$ 和 $q$ ，分别代表字符串长度和操作次数。

第二行输入一个仅由小写英文字母组成的字符串，代表初始的字符串。

接下来的 $q$ 行，每行输入两个正整数 $l$ ， $r$ ，代表操作的区间。

$1\le n\le 1000$

$1\le q\le 10$

$1\le l \le r \le 10^6$

保证每次操作时， $r$ 不大于当前的字符串长度。

输出描述

一个字符串，代表所有操作结束后形成的字符串。

样例

输入

5 3
abcde
2 4
5 8
1 3

输出

aabbbbcccddddee

样例解释

第一次操作后，字符串变成 abbccddef

第二次操作后，字符串变成 abbbccccdddef