#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];
int gar_top, gar_stack[maxn];
void release(int x) {
  gar_stack[++gar_top] = x;
}
inline int newnode(long long a) {
  int id;
  if (gar_top)
    id = gar_stack[gar_top--];
  else
    id = ++tot;
  val[id] = a, siz[id] = 1, rnd[id] = rand();
  son[id][0] = son[id][1] = 0;
  return id;
}
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];
}

long long get_min(int x) {
  while (son[x][0])
    x = son[x][0];
  return val[x];
}

int cnt1, cnt2;
void restore_dfs(int x, int& rt) {
  if (!x)
    return;
  insert(rt, val[x]);
  restore_dfs(son[x][0], rt);
  restore_dfs(son[x][1], rt);
  release(x);
}

int insert_count;

void help_merge(bool type, int t = 0) {
  if (!type) {
    int y, z;
    split(rt2, get_max(rt1) - 1, y, z);
    cnt1 += siz[y];
    assert(cnt1 <= insert_count);
    rt1 = merge(rt1, z);
    restore_dfs(y, rt1);
    rt2 = 0;
  } else {
    int x, y, z;
    int c;
    splitsz(rt1, siz[rt1] - t, rt1, c);
    split(rt2, get_min(c) - 1, x, z);
    split(z, get_max(c), y, z);
    cnt2 += siz[y];
    // assert(cnt2 <= 5e5);
    rt2 = merge(x, merge(c, z));
    restore_dfs(y, rt2);
  }
}

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


inline void work() {
  freopen("test.in", "r", stdin);
  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--;
  }
  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);
        help_merge(false);
        // 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) {
        help_merge(true, t);
        // cerr<<"t != 0 | rt2:"<<siz[rt1]<<' '<<siz[rt2]<<' '<<val[rt2]<<endl;
        while (i and a[i] / k >= h - 1) {
          insert_count++;
          insert(rt2, a[i] % k);
          i--;
        }
      }
    } else {
      int x = read();
      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;
}
/*
5 8 8
294 928 293 392 719
A 4
C 200
A 5
C 10
A 2
C 120
A 1
A 3
*/