There is a text consisting of N characters. At each step Mirko chooses two numbers A and B and then reverses the subsequence consisting of characters between indices A and B, inclusive. Indices are 1-based.

Write a program that prints the final text after all operations are made.

Input

The first line of input contains the initial text of length N (1 ≤ N ≤ 2500000). It consists only of lowercase letters of the English alphabet.

The second line contains integer M (1 ≤ M ≤ 2500), the number of steps.

Each of the following M lines contain two integer A and B (1 ≤ A ≤ B ≤ N).

Output

In the first and only line output the final text.

Example

Input: 
lukakuka
3
1 4
5 8
1 8

Output:
kukaluka

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

Output:
kubeeludomepcelluke