#include <bits/stdc++.h>
using namespace std;
template <typename T>
T POW(T base, T power) {
  T ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base);
    base = (base * base);
    power >>= 1;
  }
  return ret;
}
template <typename T>
inline T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
template <typename T>
T EUCLIDE(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <typename T>
T ABS(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
template <typename T>
T BigMod(T b, T p, T m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    T s = BigMod(b, p / 2, m);
    return ((s % m) * (s % m)) % m;
  }
  return ((b % m) * (BigMod(b, p - 1, m) % m)) % m;
}
template <typename T>
T ModInv(T b, T m) {
  return BigMod(b, m - 2, m);
}
template <typename T>
double DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
void BINARY(int n) {
  bitset<31> a = n;
  cout << a << endl;
}
void P_ARR(int *ar, int a, int b) {
  if (a > b) swap(a, b);
  if (a <= b) cout << ar[a];
  for (int i = a + 1; i <= b; i++) cout << " " << ar[i];
  cout << endl;
}
template <class T>
inline void make_unique_vec(vector<T> &vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
const double PI = 2 * acos(0);
double DEG(double x) { return (180.0 * x) / (PI * 1.0); }
double RAD(double x) { return (x * (PI * 1.0)) / (180.0); }
template <class T>
inline void make_unique_arr(T *ar, int &n) {
  sort(ar + 1, ar + n + 1);
  n = unique(ar + 1, ar + n + 1) - ar - 1;
}
int month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int ar[500007];
int ret[500007];
int idx;
struct Node {
  Node *child[2], *papa;
  bool lazy;
  int value, size;
  long long sum;
  Node() {
    child[0] = child[1] = papa = NULL;
    lazy = false;
    value = size = sum = 0;
  }
};
struct Splay_tree {
  Node *nil, *root;
  void init_tree() {
    nil = new Node();
    nil->child[0] = nil->child[1] = nil->papa = nil;
    nil->value = nil->size = nil->sum = 0;
    nil->lazy = false;
    root = nil;
  }
  void update(Node *x) {
    x->size = x->child[0]->size + x->child[1]->size + 1;
    x->sum = x->child[0]->sum + x->child[1]->sum + x->value;
  }
  void pushDown(Node *x) {
    if (x == nil) return;
    if (x->lazy) {
      swap(x->child[0], x->child[1]);
      x->child[0]->lazy = !x->child[0]->lazy;
      x->child[1]->lazy = !x->child[1]->lazy;
      x->lazy = false;
    }
  }
  void setLink(Node *x, Node *y, int d) {
    x->child[d] = y;
    y->papa = x;
  }
  int getDir(Node *x, Node *y) { return x->child[0] == y ? 0 : 1; }
  void rotate(Node *x, int d) {
    Node *y = x->child[d], *z = x->papa;
    setLink(x, y->child[d ^ 1], d);
    setLink(y, x, d ^ 1);
    setLink(z, y, getDir(z, x));
    update(x);
    update(y);
  }
  void splay(Node *x) {
    while (x->papa != nil) {
      Node *y = x->papa, *z = y->papa;
      int dy = getDir(y, x), dz = getDir(z, y);
      if (z == nil)
        rotate(y, dy);
      else if (dy == dz)
        rotate(z, dz), rotate(y, dy);
      else
        rotate(y, dy), rotate(z, dz);
    }
  }
  Node *nodeAt(Node *x, int pos) {
    while (pushDown(x), x->child[0]->size != pos)
      if (pos < x->child[0]->size)
        x = x->child[0];
      else
        pos -= x->child[0]->size + 1, x = x->child[1];
    return splay(x), x;
  }
  void split(Node *x, int cnt, Node *&t1, Node *&t2) {
    if (cnt == 0)
      t1 = nil, t2 = x;
    else {
      t1 = nodeAt(x, cnt - 1);
      t2 = t1->child[1];
      t1->child[1] = t2->papa = nil;
      update(t1);
    }
  }
  Node *join(Node *x, Node *y) {
    if (x == nil) return y;
    x = nodeAt(x, x->size - 1);
    setLink(x, y, 1);
    update(x);
    return x;
  }
  void queryAssign(int pos, int value) {
    root = nodeAt(root, pos);
    root->value = value;
    update(root);
  }
  void queryReverse(int x, int y) {
    Node *t1, *t2, *t3;
    split(root, y, t1, t3);
    split(t1, x, t1, t2);
    t2->lazy = !t2->lazy;
    root = join(join(t1, t3), t2);
  }
  void Reverse_range(int x, int y) {
    Node *t1, *t2, *t3;
    split(root, y + 1, t1, t3);
    split(t1, x, t1, t2);
    t2->lazy = !t2->lazy;
    root = join(join(t1, t2), t3);
  }
  void shift(int x, int y) {
    Node *t1, *t2, *t3, *t4, *t5, *t6;
    split(root, y + 1, t5, t6);
    split(t5, y, t3, t4);
    split(t3, x, t1, t2);
    t1 = join(t1, t4);
    t1 = join(t1, t2);
    t1 = join(t1, t6);
    root = t1;
  }
  long long querySum(int x, int y) {
    Node *t1, *t2, *t3;
    split(root, y, t1, t3);
    split(t1, x, t1, t2);
    long long sum = t2->sum;
    root = join(join(t1, t2), t3);
    return sum;
  }
  void buildTree(int n) {
    init_tree();
    root = buildTree(0, n);
  }
  Node *buildTree(int l, int r) {
    if (l == r) return nil;
    int mid = (l + r) >> 1;
    Node *x = new Node();
    x->value = ar[mid];
    x->papa = nil;
    x->lazy = false;
    setLink(x, buildTree(l, mid), 0);
    setLink(x, buildTree(mid + 1, r), 1);
    update(x);
    return x;
  }
  void show_tree() { show(root); }
  void show(Node *x) {
    if (x == nil) return;
    if (x->lazy) pushDown(x);
    show(x->child[0]);
    ret[++idx] = x->value;
    show(x->child[1]);
  }
} shaheen;
int main() {
  int n, q, m;
  scanf("%d%d%d", &(n), &(q), &(m));
  ;
  for (int i = 1; i <= n; i++) scanf("%d", &(ar[i]));
  int tot = n + 2;
  ar[n + 1] = -2;
  shaheen.buildTree(tot);
  for (int i = 1; i <= q; i++) {
    int cmd, x, y;
    scanf("%d%d%d", &(cmd), &(x), &(y));
    ;
    if (cmd == 2) {
      shaheen.Reverse_range(x, y);
    } else {
      shaheen.shift(x, y);
    }
  }
  shaheen.show_tree();
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &(x));
    ;
    { printf("%d ", ret[x + 1]); }
  }
  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;
template <typename T>
T POW(T base, T power) {
  T ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base);
    base = (base * base);
    power >>= 1;
  }
  return ret;
}
template <typename T>
inline T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
template <typename T>
T EUCLIDE(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <typename T>
T ABS(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
template <typename T>
T BigMod(T b, T p, T m) {
  if (p == 0) return 1;
  if (p % 2 == 0) {
    T s = BigMod(b, p / 2, m);
    return ((s % m) * (s % m)) % m;
  }
  return ((b % m) * (BigMod(b, p - 1, m) % m)) % m;
}
template <typename T>
T ModInv(T b, T m) {
  return BigMod(b, m - 2, m);
}
template <typename T>
double DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
void BINARY(int n) {
  bitset<31> a = n;
  cout << a << endl;
}
void P_ARR(int *ar, int a, int b) {
  if (a > b) swap(a, b);
  if (a <= b) cout << ar[a];
  for (int i = a + 1; i <= b; i++) cout << " " << ar[i];
  cout << endl;
}
template <class T>
inline void make_unique_vec(vector<T> &vec) {
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
}
const double PI = 2 * acos(0);
double DEG(double x) { return (180.0 * x) / (PI * 1.0); }
double RAD(double x) { return (x * (PI * 1.0)) / (180.0); }
template <class T>
inline void make_unique_arr(T *ar, int &n) {
  sort(ar + 1, ar + n + 1);
  n = unique(ar + 1, ar + n + 1) - ar - 1;
}
int month[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int ar[500007];
int ret[500007];
int idx;
struct Node {
  Node *child[2], *papa;
  bool lazy;
  int value, size;
  long long sum;
  Node() {
    child[0] = child[1] = papa = NULL;
    lazy = false;
    value = size = sum = 0;
  }
};
struct Splay_tree {
  Node *nil, *root;
  void init_tree() {
    nil = new Node();
    nil->child[0] = nil->child[1] = nil->papa = nil;
    nil->value = nil->size = nil->sum = 0;
    nil->lazy = false;
    root = nil;
  }
  void update(Node *x) {
    x->size = x->child[0]->size + x->child[1]->size + 1;
    x->sum = x->child[0]->sum + x->child[1]->sum + x->value;
  }
  void pushDown(Node *x) {
    if (x == nil) return;
    if (x->lazy) {
      swap(x->child[0], x->child[1]);
      x->child[0]->lazy = !x->child[0]->lazy;
      x->child[1]->lazy = !x->child[1]->lazy;
      x->lazy = false;
    }
  }
  void setLink(Node *x, Node *y, int d) {
    x->child[d] = y;
    y->papa = x;
  }
  int getDir(Node *x, Node *y) { return x->child[0] == y ? 0 : 1; }
  void rotate(Node *x, int d) {
    Node *y = x->child[d], *z = x->papa;
    setLink(x, y->child[d ^ 1], d);
    setLink(y, x, d ^ 1);
    setLink(z, y, getDir(z, x));
    update(x);
    update(y);
  }
  void splay(Node *x) {
    while (x->papa != nil) {
      Node *y = x->papa, *z = y->papa;
      int dy = getDir(y, x), dz = getDir(z, y);
      if (z == nil)
        rotate(y, dy);
      else if (dy == dz)
        rotate(z, dz), rotate(y, dy);
      else
        rotate(y, dy), rotate(z, dz);
    }
  }
  Node *nodeAt(Node *x, int pos) {
    while (pushDown(x), x->child[0]->size != pos)
      if (pos < x->child[0]->size)
        x = x->child[0];
      else
        pos -= x->child[0]->size + 1, x = x->child[1];
    return splay(x), x;
  }
  void split(Node *x, int cnt, Node *&t1, Node *&t2) {
    if (cnt == 0)
      t1 = nil, t2 = x;
    else {
      t1 = nodeAt(x, cnt - 1);
      t2 = t1->child[1];
      t1->child[1] = t2->papa = nil;
      update(t1);
    }
  }
  Node *join(Node *x, Node *y) {
    if (x == nil) return y;
    x = nodeAt(x, x->size - 1);
    setLink(x, y, 1);
    update(x);
    return x;
  }
  void queryAssign(int pos, int value) {
    root = nodeAt(root, pos);
    root->value = value;
    update(root);
  }
  void queryReverse(int x, int y) {
    Node *t1, *t2, *t3;
    split(root, y, t1, t3);
    split(t1, x, t1, t2);
    t2->lazy = !t2->lazy;
    root = join(join(t1, t3), t2);
  }
  void Reverse_range(int x, int y) {
    Node *t1, *t2, *t3;
    split(root, y + 1, t1, t3);
    split(t1, x, t1, t2);
    t2->lazy = !t2->lazy;
    root = join(join(t1, t2), t3);
  }
  void shift(int x, int y) {
    Node *t1, *t2, *t3, *t4, *t5, *t6;
    split(root, y + 1, t5, t6);
    split(t5, y, t3, t4);
    split(t3, x, t1, t2);
    t1 = join(t1, t4);
    t1 = join(t1, t2);
    t1 = join(t1, t6);
    root = t1;
  }
  long long querySum(int x, int y) {
    Node *t1, *t2, *t3;
    split(root, y, t1, t3);
    split(t1, x, t1, t2);
    long long sum = t2->sum;
    root = join(join(t1, t2), t3);
    return sum;
  }
  void buildTree(int n) {
    init_tree();
    root = buildTree(0, n);
  }
  Node *buildTree(int l, int r) {
    if (l == r) return nil;
    int mid = (l + r) >> 1;
    Node *x = new Node();
    x->value = ar[mid];
    x->papa = nil;
    x->lazy = false;
    setLink(x, buildTree(l, mid), 0);
    setLink(x, buildTree(mid + 1, r), 1);
    update(x);
    return x;
  }
  void show_tree() { show(root); }
  void show(Node *x) {
    if (x == nil) return;
    if (x->lazy) pushDown(x);
    show(x->child[0]);
    ret[++idx] = x->value;
    show(x->child[1]);
  }
} shaheen;
int main() {
  int n, q, m;
  scanf("%d%d%d", &(n), &(q), &(m));
  ;
  for (int i = 1; i <= n; i++) scanf("%d", &(ar[i]));
  int tot = n + 2;
  ar[n + 1] = -2;
  shaheen.buildTree(tot);
  for (int i = 1; i <= q; i++) {
    int cmd, x, y;
    scanf("%d%d%d", &(cmd), &(x), &(y));
    ;
    if (cmd == 2) {
      shaheen.Reverse_range(x, y);
    } else {
      shaheen.shift(x, y);
    }
  }
  shaheen.show_tree();
  for (int i = 1; i <= m; i++) {
    int x;
    scanf("%d", &(x));
    ;
    { printf("%d ", ret[x + 1]); }
  }
  return 0;
}

```