NOTE: This problem is intended to be solved last as it is quite difficult for a beginner competition.

You are given a string s of length n and m queries.

For each query you are given two integers L and R and you're asked to move the substring L to R to the start of the string.

Determine the final string after performing all the queries.

Input

Your first line will contain two space-separated integers n (n <= 250000) and m (m <= 250000).

Your next line will contain a string s of length n.

Your next m lines will contain two integers each, L and R for that query (1-indexed).

Output

You should output the final string after performing all the queries.

Input:
10 3
abcdefghij
2 3
3 5
3 7

Output:
ebcfgadhij

Explanation

Here is the string after each query.

• abcdefghij
• bcadefghij (moved 'bc' to the start since it's the substring from index 2 to 3)
• adebcfghij (moved 'ade' to the start)
• ebcfgadhij (moved 'ebcfg' to the start)