#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(),(x).end()

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (int i = 0; i < int(v.size()); i++) cout << v[i] << (i + 1 == int(v.size()) ? "" : " ");
    return os;
}

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << "(L" << __LINE__ << ")" << endl;
#else
#define debug(x)
#endif


#include <bits/extc++.h>

using namespace __gnu_pbds;
using pbds = tree<int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update>;

struct info {
    long long cur;
    long long nxt;
    int cnt;
    int pref;
    pbds d;
    int done;

    int get_kth(int k) {
        debug(k);
        debug(cnt);
        debug(pref);
        k -= pref - cnt;
        debug(k);
        if (cnt - done > k) {
            return *d.find_by_order(k + done);
        } else {
            return ~*d.find_by_order(k - (cnt - done));
        }
    }

    void exec_qry(long long &k) {
        if (done != 0) {
            if (k + done >= cnt) {
                k -= cnt - done;
                done = 0;
                cur--;
            } else {
                done += (int) k;
                k = 0;
                return;
            }
        }
        debug(k);
        debug(cur);
        debug(nxt);
        if (cur == nxt) {
            return;
        }
        long long t = min(cur - nxt, k / cnt);
        cur -= t;
        k -= t * cnt;
        if (cur == nxt) {
            return;
        }
        assert(k < cnt);
        done += (int) k;
        k = 0;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), [&](auto x, auto y) {
        return x % k < y % k;
    });
    map<long long, vector<int>> b;
    for (int i = 0; i < n; i++) {
        b[a[i] / k].emplace_back(i);
    }
    vector<info> c;
    {
        long long last_cur = -3e18;
        for (auto [i, v]: b) {
            info t = {};
            t.cur = i;
            t.nxt = last_cur;
            t.cnt = (int) v.size();
            t.pref = t.cnt;
            t.done = 0;
            for (auto j: v) {
                t.d.insert(j);
            }
            c.emplace_back(t);
            last_cur = t.cur;
        }
    }
    for (int i = (int) c.size() - 2; i >= 0; i--) {
        c[i].pref += c[i + 1].pref;
    }
    auto merge = [&]() {
        debug("merge");
        assert(c.size() >= 2);
        auto &x = c[c.size() - 1];
        auto &y = c[c.size() - 2];
        if (y.cnt < x.cnt) {
            swap(x.d, y.d);
        }
        y.cnt += x.cnt;
        for (auto i: x.d) {
            y.d.insert(i);
        }
//        y.d.join(x.d);
        c.pop_back();
    };
    auto bisect = [&](int k) {
        int low = 0, high = (int) c.size();
        while (high - low > 1) {
            auto mid = (high + low) >> 1;
            if (c[mid].pref > k) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return low;
    };
    while (m--) {
        string op;
        cin >> op;
        if (op == "A") {
            int x;
            cin >> x;
            x--;
            int s = bisect(x);
            int t = c[s].get_kth(x);
            if (t < 0) {
                cout << (c[s].cur - 1) * k + a[~t] % k << '\n';
            } else {
                cout << c[s].cur * k + a[t] % k << '\n';
            }
            debug(s);
            debug(t);
        } else {
            long long t;
            cin >> t;
            while (t > 0) {
                c.back().exec_qry(t);
                if (t > 0) {
                    merge();
                }
            }
        }
    }
    return 0;
}