Problem: Write a program which reads a sequence of integers $A = \\{a_0, a_1, ..., a_{n-1}\\}$ and reverse specified elements by a list of the following operation:

* reverse($b, e$): reverse the order of $a_b, a_{b+1}, ..., a_{e-1}$

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ...,\; a_{n-1}$
$q$
$b_1 \; e_1$
$b_2 \; e_2$
:
$b_{q} \; b_{q}$


In the first line, $n$ (the number of elements in $A$) is given. In the second line, $a_i$ (each element in $A$) are given. In the third line, the number of queries $q$ is given and each query is given by two integers $b_i \; e_i$ in the following $q$ lines.

Output

Print all elements of $A$ in a line after performing the given operations. Put a single space character between adjacency elements and a newline at the end of the last element.

Example

Input

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


Output

1 6 5 8 7 2 3 4

Solution (in JAVA):

Solution:
import java.util.ArrayList;
import java.util.Scanner;


public class Main {
//	入力値
	static Scanner scInputData = new Scanner(System.in);
//	配列
	static ArrayList<Integer> arrA = new ArrayList<Integer>();
	
	public static void main(String[] args) {
		
//		必要なパラメータを用意する処理
//		配列Aを取得する処理
		getArr(arrA);
//		reverse処理
		reverseArr();
//		結果を出力する処理
		putResult();
	}
	
	private static void putResult() {
		for(int arrNum=0; arrNum < arrA.size() - 1; arrNum++) {
			System.out.print(arrA.get(arrNum) + " ");
		}
		System.out.println(arrA.get(arrA.size() - 1));
	}

	private static void reverseArr() {
//		reverse処理の試行回数
		int revNum = scInputData.nextInt();
//		対象の範囲 (start/end)
		int start = 0, end = 0;
		for(int indexToRev = 0; indexToRev < revNum; indexToRev++) {
			start = scInputData.nextInt();
			end = scInputData.nextInt();
			reverseNum(start, end);
		}
	}

	private static void reverseNum(int start, int end) {
//		対象範囲の入替え回数
		int changeNum= (int) (end - start) / 2;

//		入替える対象の値(small側のみ)
		int val_small = 0;
		for(int indexToChange=0; indexToChange < changeNum; indexToChange++) {
			val_small = arrA.get(start + indexToChange);
			arrA.set(start + indexToChange, arrA.get(end - indexToChange - 1));
			arrA.set(end - indexToChange - 1 , val_small);
		}
	}

	private static void getArr(ArrayList<Integer> arr) {
//		 配列の要素数
		int iArrNum = 0;
		iArrNum = scInputData.nextInt();
		while(arr.size() < iArrNum) {
			arr.add(scInputData.nextInt());
		}
	}

}