Sorting Game

Time limit1sMemory limit128 MB

Summary

Apply K sets of operations, each sorting a prefix of length A ascending then a prefix of length B descending, and print the final sequence.

Level: Hard8 of 10
Topics: Sorting, Implementation, Simulation, Greedy
Solved: No attempts yet

Problem

In this game you repeatedly sort a prefix of a sequence in ascending order, then sort a prefix again in descending order. One ascending sort followed by one descending sort is one set.

For example, take the sequence [4, 1, 2, 3] and a set that sorts elements 1 through 3 in ascending order and then elements 1 through 2 in descending order. The ascending sort gives [1, 2, 4, 3], and the descending sort that follows gives [2, 1, 4, 3]. That is the sequence after the set.

You are given a sequence and $K$ sets. Write a program that prints the sequence after all $K$ sets have been carried out in the given order.

Input

The first line contains the length of the sequence, $N$ . ( $1 \le N \le 100{,}000$ )

The second line contains the $N$ elements of the sequence, separated by spaces. Each element is an integer between $-10{,}000$ and $10{,}000$ , inclusive.

The third line contains the number of sets, $K$ . ( $1 \le K \le 100{,}000$ )

Each of the next $K$ lines contains two integers $A$ and $B$ describing one set, separated by a space. ( $1 \le A \le N$ , $1 \le B \le N$ ) The set sorts elements 1 through $A$ in ascending order, then sorts elements 1 through $B$ in descending order. Carry out the sets in the order given in the input.

Output

Print the $N$ elements of the sequence after all $K$ sets, separated by spaces, on one line.

Examples4

Example 1
Input
```
4
4 1 2 3
1
3 2
```
Expected output
```
2 1 4 3
```
Example 2
Input
```
1
7
1
1 1
```
Expected output
```
7
```

Example 3

Input

6
-3 5 -3 10000 -10000 0
1
6 6

Expected output

10000 5 0 -3 -3 -10000

Example 4
Input
```
5
2 9 4 4 1
1
5 1
```
Expected output
```
1 2 4 4 9
```