OKRET - Okret

no tags 

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

hide comments
Branfili: 2012-12-01 19:25:20

@kiran
isn't it obvious?
you just switch the chars in the intervals
example 1:
lukakuka
akulkuka
akulakuk
kukaluka

(Tjandra Satria Gunawan)(曾毅昆): 2012-12-21 00:05:28

O(N+M^2)is the best complexity(?) :-D
RE (Buda IM) : is with this constraints, try similar problem TWIST

Last edit: 2012-12-21 00:06:14
Krzysztof Lewko: 2011-06-07 22:16:27

@Prateek, because it's too slow

Prateek Khandelwal: 2011-05-24 11:42:12

can someone tell me that why it can't be done by just using STL.....using some special functions provided in string library..

kiran: 2011-05-13 08:03:51

i want know explanation for the examples ....


Added by:Stjepan Glavina
Date:2011-05-06
Time limit:0.180s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian Student 2010