#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 2e5 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = a * a % M)
    if (b & 1) ret = 1ll * ret * a % M;
  return ret;
}
int a[maxn], cnt;
struct splay_tree {
  struct node {
    int val, size, son[2];
    bool rev;
    void init(int _val) {
      val = _val;
      size = 1;
      rev = son[0] = son[1] = 0;
    }
  } T[maxn * 2];
  int fa[maxn * 2], root, tot;
  void pushup(int x) {
    T[x].size = 1;
    if (T[x].son[0]) T[x].size += T[T[x].son[0]].size;
    if (T[x].son[1]) T[x].size += T[T[x].son[1]].size;
  }
  void pushdown(int x) {
    if (x == 0) return;
    if (T[x].rev) {
      if (T[x].son[0]) T[T[x].son[0]].rev ^= 1;
      if (T[x].son[1]) T[T[x].son[1]].rev ^= 1;
      swap(T[x].son[0], T[x].son[1]);
      T[x].rev = 0;
    }
  }
  void rotate(int x, int kind) {
    int y = fa[x], z = fa[y];
    T[y].son[!kind] = T[x].son[kind], fa[T[x].son[kind]] = y;
    T[x].son[kind] = y, fa[y] = x;
    T[z].son[T[z].son[1] == y] = x, fa[x] = z;
    pushup(y);
  }
  void splay(int x, int goal) {
    if (x == goal) return;
    while (fa[x] != goal) {
      int y = fa[x], z = fa[y];
      pushdown(z), pushdown(y), pushdown(x);
      int rx = T[y].son[0] == x, ry = T[z].son[0] == y;
      if (z == goal)
        rotate(x, rx);
      else {
        if (rx == ry)
          rotate(y, ry);
        else
          rotate(x, rx);
        rotate(x, ry);
      }
    }
    pushup(x);
    if (goal == 0) root = x;
  }
  int select(int pos) {
    int u = root;
    pushdown(u);
    while (T[T[u].son[0]].size != pos) {
      if (pos < T[T[u].son[0]].size)
        u = T[u].son[0];
      else {
        pos -= T[T[u].son[0]].size + 1;
        u = T[u].son[1];
      }
      pushdown(u);
    }
    return u;
  }
  void reverse(int l, int r) {
    int u = select(l - 1), v = select(r + 1);
    splay(u, 0);
    splay(v, u);
    T[T[v].son[0]].rev ^= 1;
  }
  void revolve(int l, int r, int x) {
    int u = select(r - x), v = select(r + 1);
    splay(u, 0);
    splay(v, u);
    int tmp = T[v].son[0];
    T[v].son[0] = 0;
    pushup(v);
    pushup(u);
    u = select(l - 1), v = select(l);
    splay(u, 0);
    splay(v, u);
    fa[tmp] = v;
    T[v].son[0] = tmp;
    pushup(v);
    pushup(u);
  }
  int build(int l, int r) {
    if (l > r) return 0;
    if (l == r) return l;
    int mid = (l + r) / 2;
    T[mid].son[0] = build(l, mid - 1);
    T[mid].son[1] = build(mid + 1, r);
    fa[T[mid].son[0]] = fa[T[mid].son[1]] = mid;
    pushup(mid);
    return mid;
  }
  void init(int n) {
    tot = 0;
    int i;
    T[tot++].init(INF);
    T[tot++].init(INF);
    for (i = 1; i <= n; i++) T[tot++].init(a[i]);
    T[tot++].init(INF);
    root = build(1, tot - 1);
    fa[root] = 0;
    fa[0] = 0;
    T[0].son[1] = root;
    T[0].size = 0;
  }
} T;
int root;
int L[maxn], R[maxn];
int main() {
  int i, j, k, n, q, m;
  scanf("%d%d%d", &n, &q, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  T.init(n);
  for (i = 1; i <= q; i++) {
    int k, l, r;
    scanf("%d%d%d", &k, &l, &r);
    if (k == 1) T.revolve(l, r, 1);
    if (k == 2) T.reverse(l, r);
  }
  for (i = 1; i <= m; i++) {
    int pos;
    scanf("%d", &pos);
    printf("%d ", T.T[T.select(pos)].val);
  }
}

### Prompt

In CPP, your task is to solve the following problem:

You are given an array a of size n, and q queries to it. There are queries of two types: 

  * 1 li ri — perform a cyclic shift of the segment [li, ri] to the right. That is, for every x such that li ≤ x < ri new value of ax + 1 becomes equal to old value of ax, and new value of ali becomes equal to old value of ari; 
  * 2 li ri — reverse the segment [li, ri]. 



There are m important indices in the array b1, b2, ..., bm. For each i such that 1 ≤ i ≤ m you have to output the number that will have index bi in the array after all queries are performed.

Input

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

The second line contains n integer numbers a1, a2, ..., an (1 ≤ ai ≤ 109). 

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

The last line contains m integer numbers b1, b2, ..., bm (1 ≤ bi ≤ n) — important indices of the array. 

Output

Print m numbers, i-th of which is equal to the number at index bi 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 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fll;
const long long M = 1e9 + 7;
const long long maxn = 2e5 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
template <typename T>
inline T powMM(T a, T b) {
  T ret = 1;
  for (; b; b >>= 1ll, a = a * a % M)
    if (b & 1) ret = 1ll * ret * a % M;
  return ret;
}
int a[maxn], cnt;
struct splay_tree {
  struct node {
    int val, size, son[2];
    bool rev;
    void init(int _val) {
      val = _val;
      size = 1;
      rev = son[0] = son[1] = 0;
    }
  } T[maxn * 2];
  int fa[maxn * 2], root, tot;
  void pushup(int x) {
    T[x].size = 1;
    if (T[x].son[0]) T[x].size += T[T[x].son[0]].size;
    if (T[x].son[1]) T[x].size += T[T[x].son[1]].size;
  }
  void pushdown(int x) {
    if (x == 0) return;
    if (T[x].rev) {
      if (T[x].son[0]) T[T[x].son[0]].rev ^= 1;
      if (T[x].son[1]) T[T[x].son[1]].rev ^= 1;
      swap(T[x].son[0], T[x].son[1]);
      T[x].rev = 0;
    }
  }
  void rotate(int x, int kind) {
    int y = fa[x], z = fa[y];
    T[y].son[!kind] = T[x].son[kind], fa[T[x].son[kind]] = y;
    T[x].son[kind] = y, fa[y] = x;
    T[z].son[T[z].son[1] == y] = x, fa[x] = z;
    pushup(y);
  }
  void splay(int x, int goal) {
    if (x == goal) return;
    while (fa[x] != goal) {
      int y = fa[x], z = fa[y];
      pushdown(z), pushdown(y), pushdown(x);
      int rx = T[y].son[0] == x, ry = T[z].son[0] == y;
      if (z == goal)
        rotate(x, rx);
      else {
        if (rx == ry)
          rotate(y, ry);
        else
          rotate(x, rx);
        rotate(x, ry);
      }
    }
    pushup(x);
    if (goal == 0) root = x;
  }
  int select(int pos) {
    int u = root;
    pushdown(u);
    while (T[T[u].son[0]].size != pos) {
      if (pos < T[T[u].son[0]].size)
        u = T[u].son[0];
      else {
        pos -= T[T[u].son[0]].size + 1;
        u = T[u].son[1];
      }
      pushdown(u);
    }
    return u;
  }
  void reverse(int l, int r) {
    int u = select(l - 1), v = select(r + 1);
    splay(u, 0);
    splay(v, u);
    T[T[v].son[0]].rev ^= 1;
  }
  void revolve(int l, int r, int x) {
    int u = select(r - x), v = select(r + 1);
    splay(u, 0);
    splay(v, u);
    int tmp = T[v].son[0];
    T[v].son[0] = 0;
    pushup(v);
    pushup(u);
    u = select(l - 1), v = select(l);
    splay(u, 0);
    splay(v, u);
    fa[tmp] = v;
    T[v].son[0] = tmp;
    pushup(v);
    pushup(u);
  }
  int build(int l, int r) {
    if (l > r) return 0;
    if (l == r) return l;
    int mid = (l + r) / 2;
    T[mid].son[0] = build(l, mid - 1);
    T[mid].son[1] = build(mid + 1, r);
    fa[T[mid].son[0]] = fa[T[mid].son[1]] = mid;
    pushup(mid);
    return mid;
  }
  void init(int n) {
    tot = 0;
    int i;
    T[tot++].init(INF);
    T[tot++].init(INF);
    for (i = 1; i <= n; i++) T[tot++].init(a[i]);
    T[tot++].init(INF);
    root = build(1, tot - 1);
    fa[root] = 0;
    fa[0] = 0;
    T[0].son[1] = root;
    T[0].size = 0;
  }
} T;
int root;
int L[maxn], R[maxn];
int main() {
  int i, j, k, n, q, m;
  scanf("%d%d%d", &n, &q, &m);
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  T.init(n);
  for (i = 1; i <= q; i++) {
    int k, l, r;
    scanf("%d%d%d", &k, &l, &r);
    if (k == 1) T.revolve(l, r, 1);
    if (k == 2) T.reverse(l, r);
  }
  for (i = 1; i <= m; i++) {
    int pos;
    scanf("%d", &pos);
    printf("%d ", T.T[T.select(pos)].val);
  }
}

```