#include <bits/stdc++.h>
using i64 = long long;
using i80 = __int128;
void work() {
    int n, m, q;
    i64 k;
    std::cin >> n >> m >> k;
    std::vector<i64> a(n), b, te;
    std::set<i64> set;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        set.insert(-(a[i] % k));
    }
    for (auto it : set) {
        b.push_back(-it);
    }
    q = b.size();
    std::map<i64, int> map;
    for (int i = 0; i < q; ++i) {
        map[b[i]] = i + 1;
        // std::cout << i << ";" << b[i] << "\n";
    }
    te.resize(q + 1);
    auto add = [&](int k, int x) {
        for (int i = k; i <= q; i += i & -i) {
            te[i] += x;
        }
    };
    auto ask = [&](int k) {
        int sum = 0;
        for (int i = k; i; i -= i & -i) {
            sum += te[i];
        }
        return sum;
    };
    std::sort(a.begin(), a.end(), std::greater<>());
    int rn = 1, p = 0, np;
    i64 d = a[0] / k, nd;
    add(map[a[0] % k], 1);
    while (rn < n && a[rn] / k >= d) {
        add(map[a[rn] % k], 1);
        ++rn;
    }
    while (m--) {
        std::string str;
        i64 x;
        std::cin >> str >> x;
        if (str[0] == 'C') {
            nd = d - x / rn;
            np = p + x % rn;
            if (np >= rn) {
                --nd;
                np %= rn;
            }
            // std::cout << nd << ";" << np << "|" << rn << "\n";
            while (rn < n && a[rn] / k >= nd - 1) {
                add(map[a[rn] % k], 1);
                x += d - 1 - a[rn] / k;
                ++rn;
                ++p;
                nd = d - x / rn;
                np = p + x % rn;
                if (np >= rn) {
                    --nd;
                    np %= rn;
                }
            }
            p = np, d = nd;
        } else {
            --x;
            if (x < rn) {
                int lo = 1, hi = q, mid, res;
                while (hi - lo > 1) {
                    mid = (lo + hi) / 2;
                    if ((x + p) % rn >= ask(mid - 1)) {
                        lo = mid;
                    } else {
                        hi = mid;
                    }
                }
                if ((x + p) % rn >= ask(hi - 1)) {
                    res = b[hi - 1];
                } else {
                    res = b[lo - 1];
                }
                if (x + p >= rn) {
                    std::cout << res + k * (d - 1) << "\n";
                } else {
                    std::cout << res + k * (d) << "\n";
                }
            } else {
                std::cout << a[x] << "\n";
            }
        }
        // std::cout << d << ";" << p << "|" << rn << "\n";
        // for (int i = 1; i <= q; ++i) {
        //     std::cout << ask(i) - ask(i - 1) << ",\n"[i == q];
        // }
    }
    return;
}
int main() {
    std::ios::sync_with_stdio(0);
    // std::cin.tie(0), std::cout.tie(0);
    int t = 1;
    while (t--) {
        work();
    }
}