#include <bits/stdc++.h>
using namespace std;
static constexpr int64_t inf = 0x3f3f3f3f3f3f3f3f;
uint64_t randu64(void) {
  static const auto FIXED = chrono::steady_clock::now().time_since_epoch().count();
  static mt19937_64 gen(FIXED); return gen();
} // randu64
namespace treap {
  static constexpr int MaxN = 5e5 + 5;
  struct node {
    int ls, rs, size;
    uint64_t fix;
    int64_t val;
    node() = default;
    node(int64_t v) : ls(0), rs(0), size(1), fix(randu64()), val(v) { }
  } tr[MaxN];
  int tn, root;
  int newnode(int64_t v) { return tr[++tn] = node(v), tn; }
  void pushup(int p) {
    tr[p].size = tr[tr[p].ls].size + tr[tr[p].rs].size + 1;
  } // treap::pushup
  int join(int l, int r) {
    if (!l || !r) return l | r;
    if (tr[l].fix < tr[r].fix) {
      tr[l].rs = join(tr[l].rs, r);
      return pushup(l), l;
    } else {
      tr[r].ls = join(l, tr[r].ls);
      return pushup(r), r;
    }
  } // treap::join
  void split_v(int p, int64_t v, int &l, int &r) {
    if (!p) return l = r = 0, void();
    if (tr[p].val <= v) l = p, split_v(tr[p].rs, v, tr[l].rs, r), pushup(l);
    else r = p, split_v(tr[p].rs, v, l, tr[r].rs), pushup(r);
  } // treap::split_v
  void insert(int64_t v) {
    int A, B; split_v(root, v, A, B);
    root = join(A, join(newnode(v), B));
  } // treap::insert
  int64_t find_k(int k) {
    int p = root;
    // fprintf(stderr, "k = %d, root.size = %d\n", k, tr[root].size);
    while (p) {
    // fprintf(stderr, ": k = %d, p.size = %d\n", k, tr[p].size);
      if (tr[tr[p].rs].size + 1 == k) return tr[p].val;
      if (tr[tr[p].rs].size + 1 < k)
        k -= tr[tr[p].rs].size + 1, p = tr[p].ls;
      else p = tr[p].rs;
    } return -inf;
  } // treap::find_k
  int rankv(int64_t v) {
    int p = root, y = 0;
    while (p) {
      if (tr[p].val <= v) p = tr[p].rs;
      else y += tr[tr[p].rs].size + 1, p = tr[p].ls;
    } return y;
  } // treap::rankv
} // namespace treap
using treap::insert, treap::find_k, treap::rankv;
static constexpr int Maxn = 5e5 + 5;
int n, qn, tn, cur;
int64_t K, b[Maxn], add;
int64_t modK(int64_t x) { return (x %= K) < 0 ? x + K : x; }
int64_t floorK(int64_t x) { return x - modK(x); }
int main(void) {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> qn >> K; tn = cur = 0;
  for (int i = 1; i <= n; ++i) cin >> b[i];
  sort(b + 1, b + n + 1, greater<int64_t>());
  int tn = 0; add = floorK(b[1]);
  while (tn <= n && floorK(b[tn + 1]) == add) insert(modK(b[++tn]));
  while (qn--) {
    string op; int64_t x;
    cin >> op >> x;
    if (op.front() == 'C') {
      while (x) {
        // fprintf(stderr, "x = %d, tn = %d, cur = %d\n", x, tn, cur);
        if (tn < n && floorK(b[tn + 1]) == add - K) {
          int y = rankv(modK(b[tn + 1])) - cur;
          if (y != 0) {
            if (x <= y) cur += x, x = 0;
            else cur += y, x -= y;
          }
          if (x != 0) {
            insert(modK(b[++tn])), ++cur;
          }
        } else {
          if (cur != 0) {
            if (tn - cur <= x) x -= tn - cur, cur = 0, add -= K;
            else cur += x, x = 0;
          } else {
            if (x < tn) {
              cur = x, x = 0;
            } else {
              if (tn < n) {
                int64_t p = floorK(b[tn + 1]) + K;
                if ((add - p) / K * tn <= x)
                  x -= (add - p) / K * tn, add = p;
                else add -= x / tn * K, x %= tn;
              } else {
                add -= x / tn * K, x %= tn;
              }
            }
          }
        }
      }
    } else {
      int64_t ans = inf;
      if (x <= tn - cur) ans = find_k(cur + x) + add;
      else if (x <= tn) ans = find_k(x - (tn - cur)) + add - K;
      else ans = b[x];
      cout << ans << endl;
    }
  }
  return 0;
} // main