游游的字母翻倍
题号:NC261661
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

游游拿到了一个长度为n的字符串,她每次操作会选择一个区间[l,r],将第l个字母到第r个字母各重复一次,插入到该字母的后面。
例如,对于字符串"abcd",若选择区间[2,3]进行操作,字符串将变成"abbccd"
游游将进行q次操作。她想知道,q次操作结束后,最终的字符串是什么样子?

输入描述:

第一行输入两个正整数nq,分别代表字符串长度和操作次数。
第二行输入一个仅由小写英文字母组成的字符串,代表初始的字符串。
接下来的q行,每行输入两个正整数l,r,代表操作的区间。
1\leq n \leq 1000
1\leq q \leq 10
1\leq l \leq r \leq 10^6
保证每次操作时,r不大于当前的字符串长度。

输出描述:

一个字符串,代表所有操作结束后形成的字符串。
示例1

输入

复制
6 2
abcdef
2 4
3 6

输出

复制
abbbccccdddef

说明

第一次操作后,字符串变成abbccddef
第二次操作后,字符串变成abbbccccdddef