MOVES000 - Moves

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)

Added by:jslew
Date:2022-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.