You are given an array a of size n, and q queries to it. There are queries of two types:   1 l_{i} r_{i} — perform a cyclic shift of the segment [l_{i}, r_{i}] to the right. That is, for every x such that l_{i} ≤ x < r_{i} new value of a_{x} + 1 becomes equal to old value of a_{x}, and new value of a_{l}_{i} becomes equal to old value of a_{r}_{i};  2 l_{i} r_{i} — reverse the segment [l_{i}, r_{i}].  

There are m important indices in the array b_1, b_2, ..., b_{m}. For each i such that 1 ≤ i ≤ m you have to output the number that will have index b_{i} in the array after all queries are performed.


-----Input-----

The first line contains three integer numbers n, q and m (1 ≤ n, q ≤ 2·10^5, 1 ≤ m ≤ 100). 

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). 

Then q lines follow. i-th of them contains three integer numbers t_{i}, l_{i}, r_{i}, where t_{i} is the type of i-th query, and [l_{i}, r_{i}] is the segment where this query is performed (1 ≤ t_{i} ≤ 2, 1 ≤ l_{i} ≤ r_{i} ≤ n). 

The last line contains m integer numbers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ n) — important indices of the array. 


-----Output-----

Print m numbers, i-th of which is equal to the number at index b_{i} after all queries are done.


-----Example-----
Input
6 3 5
1 2 3 4 5 6
2 1 3
2 3 6
1 1 6
2 2 1 5 3

Output
3 3 1 5 2

Difficulty: MEDIUM_HARD
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
(n, q, m) = map(int, input().split())
a = list(map(int, input().split()))
qq = list((list(map(int, input().split())) for i in range(q)))
qq = list(reversed(qq))
b = list(map(int, input().split()))
for i in range(q):
	l = qq[i][1]
	r = qq[i][2]
	if qq[i][0] == 1:
		for j in range(m):
			if b[j] < l or b[j] > r:
				continue
			if b[j] == l:
				b[j] = r
			else:
				b[j] = b[j] - 1
	else:
		for j in range(m):
			if b[j] < l or b[j] > r:
				continue
			b[j] = l + r - b[j]
for i in range(m):
	if i != m - 1:
		print(a[b[i] - 1], end=' ')
	else:
		print(a[b[i] - 1])


(n, q, m) = map(int, input().split())
a = list(map(int, input().split()))
qq = list((list(map(int, input().split())) for i in range(q)))
qq = list(reversed(qq))
b = list(map(int, input().split()))
for (qt, l, r) in qq:
	if qt == 1:
		for i in range(m):
			if l <= b[i] <= r:
				b[i] = r if b[i] == l else b[i] - 1
	else:
		for i in range(m):
			if l <= b[i] <= r:
				b[i] = r - (b[i] - l)
print(*(a[i - 1] for i in b))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, q, m) = map(int, input().split())
b = list(map(int, input().split()))
query = []
for j in range(q):
	(t, l, r) = map(int, input().split())
	query.append([t, l, r])
query.reverse()
ind = list(map(int, input().split()))
ans = []
j = 0
while j < m:
	curr = ind[j]
	i = 0
	while i < q:
		(t, l, r) = (query[i][0], query[i][1], query[i][2])
		if curr in range(l, r + 1):
			if t == 1:
				if curr == l:
					curr = r
				else:
					curr = curr - 1
			else:
				curr = r + l - curr
		i += 1
	ans.append(b[curr - 1])
	j += 1
print(*ans)


import sys
import math
from collections import defaultdict, deque

def get(ind, arr):
	n = len(arr)
	for i in range(n):
		(t, l, r) = arr[i]
		if t == 1:
			if l <= ind <= r:
				if ind == l:
					ind = r
				else:
					ind -= 1
			continue
		if t == 2:
			if l <= ind <= r:
				ind = r - ind + l
			continue
	return ind
(n, q, m) = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
l = []
for i in range(q):
	(a, b, c) = map(int, sys.stdin.readline().split())
	l.append([a, b, c])
l.reverse()
b = list(map(int, sys.stdin.readline().split()))
ans = []
for i in range(m):
	x = get(b[i], l)
	ans.append(arr[x - 1])
print(*ans)


import sys

def input():
	return sys.stdin.readline().rstrip()
DXY = [(0, -1), (1, 0), (0, 1), (-1, 0)]

def main():
	(n, q, m) = map(int, input().split())
	a = list(map(int, input().split()))
	query = [tuple(map(int, input().split())) for i in range(q)]
	indices = list(map(int, input().split()))
	for (t, l, r) in query[::-1]:
		if t == 1:
			for (i, idx) in enumerate(indices):
				if l <= idx <= r:
					if idx > l:
						indices[i] = idx - 1
					else:
						indices[i] = r
		else:
			for (i, idx) in enumerate(indices):
				if l <= idx <= r:
					indices[i] = l + r - idx
	ans = [a[idx - 1] for idx in indices]
	print(*ans)
	return 0
main()


import sys
f = lambda : list(map(int, sys.stdin.readline().split()))
q = f()[1]
a = f()
d = [f() for i in range(q)][::-1]
for k in f():
	for (t, l, r) in d:
		if l <= k <= r:
			k = l + r - k if t == 2 else r if k == l else k - 1
	print(a[k - 1])


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
(n, q, m) = map(int, input().split())
a = list(map(int, input().split()))
ops = [list(map(int, input().split())) for _ in range(q)]
b = list(map(int, input().split()))

def solve(index, ops):

	def _solve(index, op):
		(t, l, r) = op
		if index < l or index > r:
			return index
		if t == 1:
			if index == l:
				return r
			else:
				return index - 1
		else:
			return l + r - index
	for op in ops[::-1]:
		index = _solve(index, op)
	return index
b = list(map(lambda x: solve(x, ops), b))
for i in b:
	print(str(a[i - 1]) + ' ')


import sys
(n, q, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
query = [list(map(int, sys.stdin.buffer.readline().decode('utf-8').split())) for _ in range(q)]
b = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
for (qt, l, r) in reversed(query):
	if qt == 1:
		for i in range(m):
			if l <= b[i] <= r:
				b[i] = r if b[i] == l else b[i] - 1
	else:
		for i in range(m):
			if l <= b[i] <= r:
				b[i] = r - (b[i] - l)
print(*(a[i - 1] for i in b))