Reorder Reverse

Problem Statement

You are give an initial string $s$ of length $n$. You are also given $q$ queries, in order, each containing two integers $l$ and $r$ meaning you should reverse the substring from $l$ to $r$ ($0$-indexed and inclusive) of your current string (which was initially $s$ but may have undergone changes from the queries). Each query should be processed in order and you should be reversing the string after all the reverses before it had already been done.

Determine the string after all queries are done.

Input Format

Your first line will contain $n$ and $q$. Your next line will contain $s$. Your next $q$ lines will contain two integers each, representing $l$ and $r$ for that query.

Output Format

You should output the final string after all the reverse operations are performed.

Constraints

Subtask 1

• $1 \leq n, q \leq 10^3$
• $0 \leq l \leq r \leq n - 1$

Subtask 2

• $1 \leq n, q \leq 10^5$
• $0 \leq l \leq r \leq n - 1$

Sample Cases

9 3
something
1 2
1 5
0 7

nimoethsg

10 3
hellohello
0 4
5 9
0 9

hellohello