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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	(b, e) = list(map(int, input().split(' ')))
	a[b:e] = a[b:e][::-1]
print(' '.join(list(map(str, a))))


from collections import deque
import sys
input = sys.stdin.readline

def main():
	n1 = int(input())
	l1 = list(map(int, input().split()))
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		for ni in range((b - a) // 2):
			(l1[a + ni], l1[b - 1 - ni]) = (l1[b - 1 - ni], l1[a + ni])
	print(' '.join(map(str, l1)))
main()


input()
A = input().split()
for _ in [0] * int(input()):
	(b, e) = map(int, input().split())
	A = A[:b] + A[b:e][::-1] + A[e:]
print(*A)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e) = map(int, input().split())
	B = A[b:e]
	B.reverse()
	A = A[:b] + B + A[e:]
print(*A)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
Q = []
for i in range(q):
	tmp = list(map(int, input().split()))
	Q.append(tmp)
for query in Q:
	A[query[0]:query[1]] = reversed(A[query[0]:query[1]])
print(*A)


n = int(input())
box = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(a, b) = map(int, input().split())
	box = box[:a] + box[::-1][n - b:n - a] + box[b:]
print(*box)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = map(int, input().split())
	a = a[:b] + a[b:e][::-1] + a[e:]
print(*a)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = map(int, input().split())
	tmp = a[b:e]
	tmp.reverse()
	a = a[:b] + tmp + a[e:]
print(*a)


def run():
	n = int(input())
	li = input().split()
	assert len(li) == n
	q = int(input())
	for _ in range(q):
		(b, e) = [int(x) for x in input().split()]
		li = li[:b] + list(reversed(li[b:e])) + li[e:]
	print(' '.join(li))
run()


n = int(input())
s = list(map(int, input().split()))
m = int(input())
for i in range(m):
	(a, b) = map(int, input().split())
	s[a:b] = reversed(s[a:b])
print(*s)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	query = list(map(int, input().split()))
	b = A[query[0]:query[1]]
	b.reverse()
	A[query[0]:query[1]] = b
print(' '.join(map(str, A)))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = map(int, input().split())
	s = a[b:e]
	s = s[::-1]
	for j in range(e - b):
		a[b + j] = s[j]
print(*a)


n = int(input())
a = list(input().split())
q = int(input())
for i in range(q):
	(b, e) = map(int, input().split())
	a = a[:b] + a[b:e][::-1] + a[e:]
print(*a)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e) = map(int, input().split())
	a[b:e] = reversed(a[b:e])
print(' '.join(map(str, a)))


_ = input()
A = [int(a) for a in input().split()]
for _ in range(int(input())):
	(b, e) = map(int, input().split())
	A = A[0:b] + A[b:e][::-1] + A[e:]
print(*A)


n = int(input())
A = list(input().split())
q = int(input())
for i in range(q):
	queryi = list(map(int, input().split()))
	B = A[:queryi[0]]
	C = A[queryi[0]:queryi[1]]
	C.reverse()
	D = A[queryi[1]:]
	C.extend(D)
	B.extend(C)
	A = B
print(' '.join(A))


from sys import stdin
n = int(stdin.readline())
l = list(stdin.readline().split())
q = int(stdin.readline())
for i in range(q):
	inp_l = list(map(int, stdin.readline().split()))
	j = inp_l[0]
	k = inp_l[1] - 1
	while True:
		if j >= k:
			break
		(l[j], l[k]) = (l[k], l[j])
		k -= 1
		j += 1
print(' '.join(l))


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
	(b, e) = map(int, input().split())
	A = A[:b] + A[b:e][::-1] + A[e:]
print(*A)


input()
nums = list(map(int, input().split(' ')))
r = int(input())
for _ in range(r):
	(f, l) = list(map(int, input().split(' ')))
	nums = nums[:f] + list(reversed(nums[f:l])) + nums[l:]
print(' '.join(map(str, nums)))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(a, b) = map(int, input().split())
	A = A[:a] + A[a:b][::-1] + A[b:]
print(' '.join(map(str, A)))


import sys
n = int(input())
a = list(map(int, input().split()))
for _ in range(int(input())):
	(i, j) = map(int, input().split())
	a = a[:i] + a[i:j][::-1] + a[j:]
print(*a)


num = int(input())
l = [x for x in input().split()]
num = int(input())
for i in range(num):
	(a, b) = [int(x) for x in input().split()]
	l[a:b] = list(reversed(l[a:b]))
for i in range(len(l)):
	print(l[i], end='')
	if i < len(l) - 1:
		print(' ', end='')
print()


num_a = int(input())
a = list(map(lambda x: int(x), input().split()))
num_query = int(input())
for _ in range(num_query):
	(begin, end) = map(lambda x: int(x), input().split())
	if 0 == begin:
		a[begin:end] = a[end - 1::-1]
	else:
		a[begin:end] = a[end - 1:begin - 1:-1]
print(' '.join([str(elem) for elem in a]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = map(int, input().split())
	tmp = []
	for j in range((e - b) // 2):
		(a[b + j], a[e - j - 1]) = (a[e - j - 1], a[b + j])
print(*a)


n = input()
l = list(map(int, input().split()))
n = int(input())
for i in range(n):
	(b, e) = map(int, input().split())
	l1 = l[b:e]
	l1.reverse()
	l[b:e] = l1
l = map(str, l)
print(' '.join(map(str, l)))


input()
listnum = list(map(int, input().split()))
for i in range(int(input())):
	eachq = list(map(int, input().split()))
	newlist = listnum[eachq[0]:eachq[1]]
	newlist.reverse()
	listnum = listnum[:eachq[0]] + newlist + listnum[eachq[1]:]
print(' '.join(map(str, listnum)))


n = int(input())
(*a,) = map(int, input().split())
q = int(input())
while q:
	q -= 1
	(l, r) = map(int, input().split())
	a[l:r] = a[l:r][::-1]
print(*a)


def resolve():
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	ans = [i for i in range(N)]
	for _ in range(Q):
		(b, e) = [int(i) for i in input().split()]
		tmp = list(reversed(ans[b:e]))
		for i in range(b, e):
			ans[i] = tmp[i - b]
	prt = [0] * N
	for i in range(N):
		prt[i] = A[ans[i]]
	print(*prt)
resolve()


def my_reverse(ary, b, e):
	while b < e - 1:
		temp = ary[b]
		ary[b] = ary[e - 1]
		ary[e - 1] = temp
		b += 1
		e -= 1
	return ary

def main():
	input()
	ary = [int(x) for x in input().split(' ')]
	q = int(input())
	for i in range(q):
		(b, e) = [int(x) for x in input().split(' ')]
		ary = my_reverse(ary, b, e)
	print(' '.join([str(x) for x in ary]))
main()


n = int(input())
A = input().split()
n2 = int(input())
for i in range(n2):
	(a, b) = map(int, input().split())
	B = list(reversed(A[a:b]))
	A = A[0:a] + B + A[b:n]
print(*A)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = map(int, input().split())
	a = a[:b] + a[b:e][::-1] + a[e:]
print(*a)


readline = open(0).readline
N = int(readline())
(*A,) = map(int, readline().split())
Q = int(readline())
for _ in range(Q):
	(b, e) = map(int, readline().split())
	A[b:e] = reversed(A[b:e])
print(*A)


n = int(input())
a = list(map(int, input().split()))
m = int(input())
for _ in range(m):
	(b, c) = map(int, input().split())
	a[b:c] = reversed(a[b:c])
print(' '.join(map(str, a)))


n = int(input())
num = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(start, end) = map(int, input().split())
	tmp = num[start:end]
	tmp = tmp[::-1]
	num[start:end] = tmp
print(' '.join((str(n) for n in num)))


def main():
	n = input()
	seq = [int(a) for a in input().split(' ')]
	q = int(input())
	for _ in range(q):
		(b, e) = map(int, input().split(' '))
		tmp = seq[b:e]
		tmp = tmp[::-1]
		seq[b:e] = tmp[:]
	print(*seq)
main()


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = list(map(int, input().split()))
	A = A[:b] + A[b:e][::-1] + A[e:]
print(*A)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b1, b2) = map(int, input().split())
	b = a[b1:b2]
	b.reverse()
	k = 0
	for j in range(n):
		if b1 <= j < b2:
			a[j] = b[k]
			k += 1
print(a[0], end='')
for aa in a[1:]:
	print(' {}'.format(aa), end='')
print()


def partial_reverse(origin, begin, end):
	return origin[:begin] + origin[begin:end][::-1] + origin[end:]
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
	(b, e) = map(int, input().split())
	A = partial_reverse(A, b, e)
print(' '.join(map(str, A)))


n = int(input())
arr = input().split()
nq = int(input())
for i in range(nq):
	(b, e) = map(int, input().split())
	arr = arr[:b] + arr[b:e][::-1] + arr[e:]
print(*arr)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(x, y) = map(int, input().split())
	a[x:y] = reversed(a[x:y])
print(*a)


def solve():
	from sys import stdin
	f_i = stdin
	n = f_i.readline()
	A = f_i.readline().split()
	q = int(f_i.readline())
	for i in range(q):
		(b, e) = map(int, f_i.readline().split())
		r = A[b:e]
		r.reverse()
		A = A[:b] + r + A[e:]
	print(' '.join(A))
solve()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e) = list(map(int, input().split()))
	if b == 0:
		a = a[e - 1::-1] + a[e:]
	else:
		a = a[:b] + a[e - 1:b - 1:-1] + a[e:]
print(' '.join(map(str, a)))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e) = list(map(int, input().split()))
	a0 = a[:b]
	a1 = a[b:e]
	a3 = a[e:]
	a1r = a1[::-1]
	a = a0 + a1r + a3
print(*a, sep=' ')