Reversal

A text editor holds a string of $N$ characters. Mirko performs $M$ steps. In each step he picks two numbers $A$ and $B$ and reverses the substring made of all characters from position $A$ to position $B$, inclusive. To reverse it, he swaps the first character of the substring with the last one, the second with the second to last, and so on. Positions in the string are numbered from $1$ to $N$.

Write a program that finds the final state of the string after all reversals.

The first line contains the initial string. It consists only of lowercase English letters, and its length $N$ is at most $2\,500\,000$. The second line contains a positive integer $M$ ($1 \le M \le 2\,500$), the number of steps. Each of the next $M$ lines contains two positive integers $A$ and $B$ ($1 \le A \le B \le N$) that describe one step.

Print the string after all reversals on a single line.