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: interview

Starter code:

Solutions:
# https://codeforces.com/contest/863/problem/D


from sys import stdin, stdout
input = stdin.readline
print = stdout.write
# solve the reversed problem
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])+" ")

# Cartesian tree:
# https://codeforces.com/contest/863/submission/30693678


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)