Reversing Subarrays

You are given an array, which you will need to reverse ~x~ times at a given starting index, and an ending index, both inclusive.

Input Specification

The first line of input is the size of the array ~n~ ~(10 \le n \le 1000)~.

In the next line, there are ~n~ space-separated integers that represent the values in the array, where ~(0 \le a_i \le 20)~.

The next line has the integer ~x~ ~(1 \le x \le 10)~ which is how many times the array is to be reversed.

The next ~x~ lines each have 2 space-separated integers ~(0 \le k_1 \le k_2 < n)~ representing the starting index and the ending index, respectively.

Output Specification

Print out the array with each element separated by a space after each reversal.

Sample Input

10
1 2 3 4 5 6 7 8 9 10
2
0 9
3 8

Sample Output

10 9 8 7 6 5 4 3 2 1
10 9 8 2 3 4 5 6 7 1