题目描述

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

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

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

输入描述

第一行输入两个正整数 $n,q(1\le n\le 1000,1\le q\le 10)$ ，分别代表字符串长度和操作次数。

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

接下来的 $q$ 行，每行输入两个正整数$l,r(1\le l,r\le 10^6)$ ，代表操作的区间。

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

输出描述

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

样例

输入

5 3
abcde
2 4
5 8
1 3

输出

aabbbbcccddddee

样例解释

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

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