Range Sorting

Problem Description

Xiao Yang has a sequence $a$ of $n$ positive integers.

He plans to sort the sequence in ascending order several times. Each time, he chooses an interval $[l, r]$ ($l \le r$) and sorts the numbers $a_l, a_{l+1}, \dots, a_r$ within that interval in ascending order. Each sort is performed on top of the result of the previous sort.

Xiao Yang asks you to compute the sequence after all the ascending sorts.

Input Format

The first line contains a positive integer $n$, as described.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, the sequence $a$.

The third line contains a positive integer $q$, the number of sorts.

Each of the following $q$ lines contains two positive integers $l, r$, meaning that all numbers in the interval $[l_i, r_i]$ are sorted in ascending order.

Output Format

Output one line containing $n$ positive integers: the sequence after all the ascending sorts.

Sample Input

5
3 4 5 2 1
3
4 5
3 4
1 3

Sample Output

1 3 4 5 2

Sample Explanation

For the sample, the initial sequence is $[3, 4, 5, 2, 1]$.

• First sort: interval $[4, 5]$, sort the 4th and 5th numbers $2, 1$ in ascending order → sequence becomes $[3, 4, 5, 1, 2]$.
• Second sort: interval $[3, 4]$, sort the 3rd and 4th numbers $5, 1$ in ascending order → sequence becomes $[3, 4, 1, 5, 2]$.
• Third sort: interval $[1, 3]$, sort the 1st to 3rd numbers $3, 4, 1$ in ascending order → sequence becomes $[1, 3, 4, 5, 2]$.

The final output sequence is $1\ 3\ 4\ 5\ 2$.

Constraints

For all test data, $1 \le n, a_i, q \le 100$ and $1 \le l_i \le r_i \le n$ are guaranteed.