No tag edit access

D. Yet Another Array Queries Problem

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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*_{li}becomes equal to old value of*a*_{ri}; - 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

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2019 16:23:02 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|