#include <bits/stdc++.h>
using namespace std;
#define int long long
inline long long read() {
  int w = 0;
  long long x = 0;
  char c = getchar();
  while (!isdigit(c)) w |= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  return w ? -x : x;
}
namespace star {
const int maxn = 2 * 5e5 + 10;
inline char gc() {
  char c = getchar();
  while (isspace(c)) c = getchar();
  return c;
}
int n, m;
long long k, a[maxn];
#define ls son[ro][0]
#define rs son[ro][1]
int son[maxn][2], siz[maxn], tot, rnd[maxn], rt1, rt2;
long long val[maxn];
inline int newnode(long long a) {
  val[++tot] = a, siz[tot] = 1, rnd[tot] = rand();
  return tot;
}
inline void pushup(const int &ro) { siz[ro] = siz[ls] + siz[rs] + 1; }
int merge(int a, int b) {
  if (!a or !b) return a | b;
  if (rnd[a] < rnd[b]) {
    son[a][1] = merge(son[a][1], b);
    pushup(a);
    return a;
  } else {
    son[b][0] = merge(a, son[b][0]);
    pushup(b);
    return b;
  }
}
void split(int ro, long long k, int &a, int &b) {
  if (!ro) return a = b = 0, void();
  if (val[ro] <= k)
    a = ro, split(rs, k, rs, b);
  else
    b = ro, split(ls, k, a, ls);
  pushup(ro);
}
inline void insert(int &rt, long long a) {
  int x, y;
  split(rt, a, x, y);
  rt = merge(merge(x, newnode(a)), y);
}
void splitsz(int ro, int k, int &a, int &b) {
  if (!ro) return a = b = 0, void();
  if (siz[ls] + 1 <= k)
    a = ro, splitsz(rs, k - siz[ls] - 1, rs, b);
  else
    b = ro, splitsz(ls, k, a, ls);
  pushup(ro);
}
inline void del(int &rt, int a) {
  int x, y, z;
  split(rt, a - 1, x, z);
  splitsz(z, 1, y, z);
  rt = merge(x, z);
}
long long get_max(int x) {
  while (son[x][1])
    x = son[x][1];
  return val[x];
}
inline long long kth(int ro, int a) {
  while (true) {
    // std::cerr << val[ro] << " ? " << std::endl;
    if (a <= siz[ls])
      ro = ls;
    else {
      a -= siz[ls];
      if (--a == 0) return val[ro];
      ro = rs;
    }
  }
}
#undef ls
#undef rs
void restore_dfs(int x) {
  if (!x)
    return;
  insert(rt1, val[x]);
  restore_dfs(son[x][0]);
  restore_dfs(son[x][1]);
}

inline void work() {
  n = read(), m = read(), k = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  sort(a + 1, a + 1 + n);
  long long h = a[n] / k, i = n;
  while (i and a[i] / k == h) {
    insert(rt1, a[i] % k);
    i--;
  }
  int CNT = 0;
  while (m--) {
    // cerr<<"Before:"<<h<<' '<<siz[rt1]<<' '<<siz[rt2]<<endl;
    if (gc() == 'C') {
      long long t = read();
      if (t >= siz[rt1]) {
        t -= siz[rt1];
        // for (auto x : hold) del(rt2, x);
        int x;
        split(rt2, get_max(rt1), x, rt2);
        rt1 = merge(rt1, rt2);
        rt2 = 0;
        restore_dfs(x);
        // for (auto x : hold) insert(rt1, x);
        h--;
      }
      while (i and (h - a[i] / k) * siz[rt1] < t /* 这个用除法是不是会判少了*/ ) {
        assert(siz[rt2] == 0);
        t -= (h - a[i] / k) * siz[rt1];
        h = a[i] / k;
        insert(rt1, a[i] % k);
        i--;
      }
      h -= t / siz[rt1];
      // t -= (t / siz[rt1]) * siz[rt1];
      t %= siz[rt1];
      if (t) {
        int c;
        splitsz(rt1, siz[rt1] - t, rt1, c);
        rt2 = merge(c, rt2);
        t = 0;
        // cerr<<"rt2:"<<siz[rt1]<<' '<<siz[rt2]<<' '<<val[rt2]<<endl;
        while (i and a[i] / k >= h - 1) {
          // hold.push_back(a[i] % k);
          insert(rt2, a[i] % k);
          i--;
        }
      }
    } else {
      int x = read();
      ++CNT;
      if (CNT == 18)
        printf("??? CASE %d %d\n", x > siz[rt1] + siz[rt2], x > siz[rt1]);
      if (x > siz[rt1] + siz[rt2]) {
        printf("%lld\n", a[n - x + 1]);
      } else if (x > siz[rt1]) {
        // cerr<<"AAAAAAA:"<<h<<' '<<siz[rt1]<<'
        // '<<siz[rt2]-(x-siz[rt1])+1<<endl;
        printf("%lld\n", k * (h - 1) + kth(rt2, siz[rt2] - (x - siz[rt1]) + 1));
      } else
        printf("%lld\n", k * h + kth(rt1, siz[rt1] - x + 1));
    }
    // cerr<<"After:"<<h<<' '<<siz[rt1]<<' '<<siz[rt2]<<endl<<endl;
  }
}
}  // namespace star
signed main() {
  star::work();
  return 0;
}