#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(const char *s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(const char *s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  for (int f = 0; L != R; ++f)
    cerr << (f++ ? ", " : "") << *L++;
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

mt19937 rnd(7122);

struct treap {
  lld v, add;
  uint32_t size, pri;
  treap *lc, *rc;
  explicit treap(lld x) : v(x), add(0), size(1), pri(rnd()), lc(nullptr), rc(nullptr) {}
  void pull() {
    size = 1;
    if (lc)
      size += lc->size;
    if (rc)
      size += rc->size;
  }
  void push() {
    if (lc) {
      lc->v += add;
      lc->add += add;
    }
    if (rc) {
      rc->v += add;
      rc->add += add;
    }
    add = 0;
  }
};

treap *merge(treap *l, treap *r) {
  if (not l or not r) return l ? l : r;
  if (l->pri > r->pri) {
    l->push();
    l->rc = merge(l->rc, r);
    l->pull();
    return l;
  } else {
    r->push();
    r->lc = merge(l, r->lc);
    r->pull();
    return r;
  }
}

#define sz(x) int((x) ? (x)->size : 0)

void split_by_size(treap *o, int k, treap *&l, treap *&r) {
  if (not o) l = r = nullptr;
  else if (int s = sz(o->lc) + 1; s <= k) {
    l = o;
    l->push();
    split_by_size(o->rc, k - s, l->rc, r);
    l->pull();
  } else {
    r = o;
    r->push();
    split_by_size(o->lc, k, l, r->lc);
    r->pull();
  }
}

void split_by_key(treap *o, lld k, treap *&l, treap *&r) {
  if (not o) l = r = nullptr;
  else if (o->v <= k) {
    l = o;
    l->push();
    split_by_key(o->rc, k, l->rc, r);
    l->pull();
  } else {
    r = o;
    r->push();
    split_by_key(o->lc, k, l, r->lc);
    r->pull();
  }
}

treap *o;

void insert(lld x) {
  treap *cur = new treap(x);
  treap *l, *r;
  split_by_key(o, x, l, r);
  o = merge(l, merge(cur, r));
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, q;
  lld k;
  cin >> n >> q >> k;
  vector<lld> v(n);
  for (auto &vi : v)
    cin >> vi;
  sort(v.begin(), v.end());
  insert(v.back());
  int p = n - 2;
  auto adjust = [&] {
    treap *a, *b;
    split_by_size(o, o->size - 1, a, b);
    o = merge(a, b);
    lld x = b->v;
    while (p >= 0 and x - v[p] < k) {
      insert(v[p--]);
    }
  };
  while (q--) {
    adjust();
    string op;
    lld x;
    cin >> op >> x;
    if (op == "A") {
      if (x > int(o->size)) {
        cout << v[p - (x - o->size) + 1] << '\n';
      } else {
        treap *a, *b, *c, *d;
        split_by_size(o, o->size - x, a, b);
        split_by_size(b, 1, c, d);
        cout << c->v << '\n';
        o = merge(a, merge(c, d));
      }
    } else {
      while (p >= 0) {
        treap *a, *b;
        split_by_size(o, o->size - 1, a, b);
        o = merge(a, b);
        lld la = b->v;
        
        lld t = (la - k - v[p] + k - 1) / k;
        lld tt = t * o->size;
        if (x >= tt) {
          o->v -= k * t;
          o->add -= k * t;
          x -= tt;
        } else {
          break;
        }
        insert(v[p--]);
        adjust();
      }
      o->v -= k * (x / o->size);
      o->add -= k * (x / o->size);
      x %= o->size;
      treap *a, *b;
      split_by_size(o, o->size - x, a, b);
      b->v -= k;
      b->add -= k;
      o = merge(b, a);
    }
  }
  return 0;
}