Yet Another Array Queries Problem

2000ms

262144K

Description:

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₁, b₂, ..., 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⁵, 1 ≤ m ≤ 100).

The second line contains n integer numbers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹).

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₁, b₂, ..., 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.

Sample Input:

6 3 5
1 2 3 4 5 6
2 1 3
2 3 6
1 1 6
2 2 1 5 3

Sample Output:

3 3 1 5 2

Informação

Provedor Codeforces

Código CF863D