Reversal

Interview

Time limit1sMemory limit256 MB

Summary

Apply M substring reversals to a string of up to 2.5 million characters and print the final result.

Level: Easy3 of 10
Topics: String, Implementation, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

Print the string after all reversals on a single line.

Examples2

Example 1
Input
```
lukakuka
3
1 4
5 8
1 8
```
Expected output
```
kukaluka
```

Example 2

Input

kukulelebodumepcele
5
3 7
10 12
2 10
5 18
5 15

Expected output

kubeeludomepcelluke