#include <bits/stdc++.h>
using namespace std;
istream& in = cin;
ostream& out = cout;
template <class T>
void outputArray(const vector<T>& ar, ostream& out) {
  for (size_t i = 0; i < ar.size(); ++i) out << ar[i] << " ";
  out << endl;
}
typedef struct Item* PItem;
struct Item {
  Item(int val, int prior)
      : value(val),
        prior(prior),
        cnt(0),
        needReverse(false),
        left(NULL),
        right(NULL) {}
  int prior, value, cnt;
  bool needReverse;
  PItem left, right;
};
int cnt(PItem item) {
  if (item != NULL)
    return item->cnt;
  else
    return 0;
}
void updateCnt(PItem item) {
  if (item) item->cnt = cnt(item->left) + cnt(item->right) + 1;
}
void push(PItem item) {
  if (item && item->needReverse) {
    item->needReverse = false;
    swap(item->left, item->right);
    if (item->left) item->left->needReverse ^= true;
    if (item->right) item->right->needReverse ^= true;
  }
}
void split(PItem t, PItem& l, PItem& r, int key, int add = 0) {
  if (t == NULL) return void(l = r = NULL);
  push(t);
  int cur_key = add + cnt(t->left);
  if (key <= cur_key)
    split(t->left, l, t->left, key, add), r = t;
  else
    split(t->right, t->right, r, key, add + 1 + cnt(t->left)), l = t;
  updateCnt(t);
}
void merge(PItem& t, PItem l, PItem r) {
  push(l);
  push(r);
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge(l->right, l->right, r), t = l;
  else
    merge(r->left, l, r->left), t = r;
  updateCnt(t);
}
void reverse(PItem t, int l, int r) {
  PItem t1, t2, t3;
  split(t, t1, t2, l);
  split(t2, t2, t3, r - l + 1);
  if (t2) t2->needReverse ^= true;
  merge(t, t1, t2);
  merge(t, t, t3);
}
void shiftRight(PItem t, int l, int r) {
  PItem a, b, c, d, lef, rgh;
  split(t, a, b, r + 1);
  split(a, c, d, l);
  split(d, lef, rgh, r - l);
  merge(a, c, rgh);
  merge(b, lef, b);
  merge(t, a, b);
}
void insert(PItem& t, int pos, PItem newIt) {
  if (!t) {
    t = newIt;
  } else {
    PItem t1, t2;
    split(t, t1, t2, pos);
    merge(t1, t1, newIt);
    merge(t, t1, t2);
  }
}
void search(PItem t, int pos, PItem& res, int add = 0) {
  if (!t) {
    res = NULL;
    exit;
  }
  push(t);
  int cur_key = add + cnt(t->left);
  if (pos == cur_key) {
    res = t;
    return;
  } else if (pos < cur_key)
    search(t->left, pos, res, add);
  else
    search(t->right, pos, res, add + 1 + cnt(t->left));
}
void output(PItem t, vector<int>& res) {
  if (t == NULL) return;
  push(t);
  output(t->left, res);
  out << t->value << " ";
  output(t->right, res);
}
struct ItemIdx {
  int value;
  int index;
  ItemIdx(int value, int index) : value(value), index(index) {}
  bool operator<(const ItemIdx& rhs) { return value < rhs.value; }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  size_t n, q, m;
  in >> n >> q >> m;
  vector<ItemIdx> Ar;
  int num;
  for (size_t i = 0; i < n; ++i) {
    in >> num;
    Ar.push_back(ItemIdx(num, i));
  }
  PItem treap = NULL;
  for (size_t i = 0; i < n; ++i) {
    PItem item = new Item(Ar[i].value, Ar[i].value);
    insert(treap, i, item);
  }
  for (size_t i = 0; i < q; ++i) {
    size_t t, l, r;
    in >> t >> l >> r;
    if (t == 1)
      shiftRight(treap, l - 1, r - 1);
    else
      reverse(treap, l - 1, r - 1);
    vector<int> ans;
  }
  for (size_t i = 0; i < m; ++i) {
    size_t pos;
    PItem res;
    in >> pos;
    search(treap, pos - 1, res);
    out << res->value << " ";
  }
  out << endl;
  return 0;
}

### Prompt

Generate a cpp solution to 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;
istream& in = cin;
ostream& out = cout;
template <class T>
void outputArray(const vector<T>& ar, ostream& out) {
  for (size_t i = 0; i < ar.size(); ++i) out << ar[i] << " ";
  out << endl;
}
typedef struct Item* PItem;
struct Item {
  Item(int val, int prior)
      : value(val),
        prior(prior),
        cnt(0),
        needReverse(false),
        left(NULL),
        right(NULL) {}
  int prior, value, cnt;
  bool needReverse;
  PItem left, right;
};
int cnt(PItem item) {
  if (item != NULL)
    return item->cnt;
  else
    return 0;
}
void updateCnt(PItem item) {
  if (item) item->cnt = cnt(item->left) + cnt(item->right) + 1;
}
void push(PItem item) {
  if (item && item->needReverse) {
    item->needReverse = false;
    swap(item->left, item->right);
    if (item->left) item->left->needReverse ^= true;
    if (item->right) item->right->needReverse ^= true;
  }
}
void split(PItem t, PItem& l, PItem& r, int key, int add = 0) {
  if (t == NULL) return void(l = r = NULL);
  push(t);
  int cur_key = add + cnt(t->left);
  if (key <= cur_key)
    split(t->left, l, t->left, key, add), r = t;
  else
    split(t->right, t->right, r, key, add + 1 + cnt(t->left)), l = t;
  updateCnt(t);
}
void merge(PItem& t, PItem l, PItem r) {
  push(l);
  push(r);
  if (!l || !r)
    t = l ? l : r;
  else if (l->prior > r->prior)
    merge(l->right, l->right, r), t = l;
  else
    merge(r->left, l, r->left), t = r;
  updateCnt(t);
}
void reverse(PItem t, int l, int r) {
  PItem t1, t2, t3;
  split(t, t1, t2, l);
  split(t2, t2, t3, r - l + 1);
  if (t2) t2->needReverse ^= true;
  merge(t, t1, t2);
  merge(t, t, t3);
}
void shiftRight(PItem t, int l, int r) {
  PItem a, b, c, d, lef, rgh;
  split(t, a, b, r + 1);
  split(a, c, d, l);
  split(d, lef, rgh, r - l);
  merge(a, c, rgh);
  merge(b, lef, b);
  merge(t, a, b);
}
void insert(PItem& t, int pos, PItem newIt) {
  if (!t) {
    t = newIt;
  } else {
    PItem t1, t2;
    split(t, t1, t2, pos);
    merge(t1, t1, newIt);
    merge(t, t1, t2);
  }
}
void search(PItem t, int pos, PItem& res, int add = 0) {
  if (!t) {
    res = NULL;
    exit;
  }
  push(t);
  int cur_key = add + cnt(t->left);
  if (pos == cur_key) {
    res = t;
    return;
  } else if (pos < cur_key)
    search(t->left, pos, res, add);
  else
    search(t->right, pos, res, add + 1 + cnt(t->left));
}
void output(PItem t, vector<int>& res) {
  if (t == NULL) return;
  push(t);
  output(t->left, res);
  out << t->value << " ";
  output(t->right, res);
}
struct ItemIdx {
  int value;
  int index;
  ItemIdx(int value, int index) : value(value), index(index) {}
  bool operator<(const ItemIdx& rhs) { return value < rhs.value; }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  size_t n, q, m;
  in >> n >> q >> m;
  vector<ItemIdx> Ar;
  int num;
  for (size_t i = 0; i < n; ++i) {
    in >> num;
    Ar.push_back(ItemIdx(num, i));
  }
  PItem treap = NULL;
  for (size_t i = 0; i < n; ++i) {
    PItem item = new Item(Ar[i].value, Ar[i].value);
    insert(treap, i, item);
  }
  for (size_t i = 0; i < q; ++i) {
    size_t t, l, r;
    in >> t >> l >> r;
    if (t == 1)
      shiftRight(treap, l - 1, r - 1);
    else
      reverse(treap, l - 1, r - 1);
    vector<int> ans;
  }
  for (size_t i = 0; i < m; ++i) {
    size_t pos;
    PItem res;
    in >> pos;
    search(treap, pos - 1, res);
    out << res->value << " ";
  }
  out << endl;
  return 0;
}

```