#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using i64 = int64_t;
using u64 = int64_t;
using f64 = double_t;
constexpr i64 mod = 998244353;
i64 div_f(i64 x, i64 k) { return x / k - (x < 0 and x % k); }
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n, m;
  i64 k;
  cin >> n >> m >> k;
  vector<i64> a(n);
  for (i64 &ai : a) { cin >> ai; }
  ranges::sort(a);
  tree<pair<i64, int>, null_type, less<pair<i64, int>>, rb_tree_tag,
       tree_order_statistics_node_update>
      top;
  i64 d = div_f(a.back(), k), vir = 0;
  int st = n - 1;
  auto flush = [&]() {
    while (st >= 0) {
      i64 di = div_f(a[st], k);
      if (di == d) {
        top.insert({a[st] - d * k, st});
      } else if (di == d - 1 and
                 a[st] >= top.find_by_order(top.size() - vir - 1)->first) {
        vir += 1;
        top.insert({a[st] - d * k + k, st});
      } else {
        break;
      }
      st -= 1;
    }
  };
  flush();
  for (int i = 0; i < m; i += 1) {
    char c;
    cin >> c;
    if (c == 'C') {
      i64 t;
      cin >> t;
      while (t > 0) {
        if (top.size() - vir > t) {
          vir += t;
          flush();
          break;
        }
        if (vir > 0) {
          t -= top.size() - vir;
          vir = 0;
          d -= 1;
          flush();
        } else if (st == -1) {
          d -= t / top.size();
          t %= top.size();
        } else {
          i64 x = min(d - div_f(a[st], k), t / (int)top.size());
          d -= x;
          t -= x * top.size();
          flush();
        }
      }
    } else {
      int x;
      cin >> x;
      if (x > top.size()) {
        cout << a[n - x] << "\n";
        continue;
      } else if (x <= top.size() - vir) {
        cout << top.find_by_order(top.size() - vir - x)->first + d * k << "\n";
      } else {
        cout << top.find_by_order(top.size() - x + (top.size() - vir))->first +
                    (d - 1) * k
             << "\n";
      }
    }
  }
}