As is known to all, the operating system of Yuangq‘s computer(that picked up from the garbage dump) is rubbidows system, and rubbidows system always makes Yuangq feels blackout in unexpected ways...
 
The Spring Festival is coming, and Yuangq sends his best friend Waylon a greeting message: Happy new year!. However, as he typed Happy, the screen displayed pypHa...
 
Yuangq has no idea what happened, so he started messing around with the system. After a series of wired operations, he found that the  rubbidows system would automatically press the home key or end key off and on.

Fortunately, Waylon provided an accurate hint: the rubbidows system will perform operation  () at second , where operation  involves automatically pressing the home key, and operation  involves automatically pressing the end key.
 
The start time is  second, and it takes  second to enter each character. The operation must be performed after the character entering. In other words, if , then only after rubbidows system typing the  character, will the rubbidows system automatically press the home or end key.

Since Yuangq had spent all his money on buying gifts, he didn't have enough money to buy the official Rubbish&Windows version, so Yuangq decided to input in a different way. He wants to know in what order he has to input to make the string be input correctly.

About the home and end keys: 
The home key moves the cursor to the first word on the first line of the editing or non-editing window. The end key is just the opposite, and the cursor will be positioned at the end.

输入描述:

The first line inputs a string  ( ), representing the string to be input for Yuangq , which contains only uppercase letters, lowercase letters and numbers.

On the second line, input a positive integer ( ) which represents the number of operations performed by the  rubbidows system.

Then following  lines, input two positive integers  () for each line, whose meanings are as described above.

It is guarenteed that all  operations satisfy strict monotonic increase of . What's more, there are no two adjacent operations where  is equal to .

输出描述:

Output only one string, representing the input order in which Yuangq can type his desired string.

HappyNewYear
4
2 1
4 1
8 1
11 1

arYeyNewappH

Let's use "#" to represent the cursor, and each line break represents the next second:

1.a#  
2.#ar  
3.Y#ar  
4.#Year  
5.y#Year  
6.yN#Year  
7.yNe#Year  
8.#yNewYear  
9.a#yNewYear  
10.ap#yNewYer  
11.#appyNewYear  
12.H#appyNewYear

(Removing the cursor will result in Happy New Year)

fengxiaoyi
4
3 1
4 2
7 1
8 2

ngxeiaofyi

1. n#
2. ng#
3. #ngx
4. engx#
5. engxi#
6. engxia#
7. #engxiao
8. fengxiao#
9. fengxiaoy#
10. fengxiaoyi#

(Removing the cursor will result in fengxiaoyi)

savioawnuqmcoqwyeuappcwqeweromxazpiew8702341
8
2 1
4 2
10 1
15 1
25 2
30 1
37 2
42 1

erewomxazpppcwqqmcoqwyeuaiew87vioawnu02341sa

备注: