Yet Another Array Queries Problem CodeForces

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.

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 

题意：
对一个数组，有两种操作，１：翻转　２　左移
问所有操作完成后，位置ｐ的数是多大．
思路：
对于当前操作，之后的操作与之无关，所以直接暴力反推，ｐ由哪个位置转移来即可

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>

#define fuck(x) cerr<<#x<<" = "<<x<<endl;
#define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl;
#define ls (t<<1)
#define rs ((t<<1)|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int loveisblue = 486;
const int maxn = 200086;
const int maxm = 100086;
const int inf = 0x3f3f3f3f;
const ll Inf = 999999999999999999;
const int mod = 1000000007;
const double eps = 1e-6;
const double pi = acos(-1);

int num[maxn];
struct node{
    int l,r,type;
}a[maxn];
int main() {
//    ios::sync_with_stdio(false);
//    freopen("in.txt", "r", stdin);

    int n,q,m;
    scanf("%d%d%d",&n,&q,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
    }
    for(int i=1;i<=q;i++){
        scanf("%d%d%d",&a[i].type,&a[i].l,&a[i].r);
    }

    while (m--){
        int x;
        scanf("%d",&x);
        for(int i=q;i>=1;i--){
            if(a[i].l>x||a[i].r<x){ continue;}
            if(a[i].type==1){
                if(a[i].l==x){
                    x=a[i].r;
                }else {
                    x--;
                }
            }else{
                int y = a[i].r - x;
                x = a[i].l+y;
            }
        }
        printf("%d ",num[x]);
    }


    return 0;
}

View Code