// #pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define PB emplace_back
// #define int long long
#define ll long long
#define vi vector<int>
#define siz(a) ((int) ((a).size()))
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
void print(vi n) {rep(i, 0, siz(n) - 1) cerr << n[i] << " \n"[i == siz(n) - 1];}

const int N = 5e5;
int a, b, c, rt;
struct pii {
	int x, y;
	bool operator<(const pii &o) const {return x < o.x || (x == o.x && y < o.y);}
} s[N + 5];
int ls[N + 5], rs[N + 5], rnd[N + 5], siz[N + 5], w[N + 5], id;
int New(int n) {
	++id;
	siz[id] = 1;
	w[id] = n;
	rnd[id] = rand();
	return id;
}
void up(int n) {
	siz[n] = siz[ls[n]] + siz[rs[n]] + 1;
}
// void spl(int n, int k, int &x, int &y) {
// 	if(!n) return x = y = 0, void();
// 	if(siz[n] <= k) x = n, spl(rs[n], k, rs[n], y), up(n);
// 	else y = n, spl(ls[n], k, x, ls[n]), up(n);
// }
void slt(int n, int k, int &x, int &y) {
	if(!n) return x = y = 0, void();
	if(w[n] <= k) x = n, slt(rs[n], k, rs[n], y), up(n);
	else y = n, slt(ls[n], k, x, ls[n]), up(n);
}
int mer(int n, int m) {
	if(!n || !m) return n + m;
	if(rnd[n] < rnd[m]) return rs[n] = mer(rs[n], m), up(n), n;
	else return ls[m] = mer(n, ls[m]), up(m), m;
}
void ins(int n) {
	int x, y;
	slt(rt, n, x, y);
	rt = mer(mer(x, New(n)), y);
}
int ask(int n, int m) {
	if(m == siz[ls[n]] + 1) return w[n];
	if(m <= siz[ls[n]]) return ask(ls[n], m);
	else return ask(rs[n], m - siz[ls[n]] - 1);
}

signed main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> a >> b >> c;
	int x;
	char y;
	rep(i, 1, a) cin >> x, s[i] = pii {x / c, x % c};
	sort(s + 1, s + a + 1);
	int now = 0, r = a - 1, R = s[a].x, sz = 1;
	ins(s[a].y);
	rep(i, 1, b) {
		cin >> y >> x;
		if(y == 'C') now += x;
		else {
			while(r && (R - s[r].x) * sz <= now) {
				now -= (R - s[r].x) * sz;
				ins(s[r].y);
				R = s[r].x;
				++sz;
				--r;
			}
			if(x > sz) {
				// cout << r - (x - sz) + 1 << "#@!@#@" << sz << endl;
				cout << s[r - (x - sz) + 1].x * c + s[r - (x - sz) + 1].y << '\n';
				continue;
			}
			int ans = s[r + 1].x - now / sz, z = sz - now % sz;
			// cout << i << ' ' << r << ' ' << now << ' ' << z << "#@!#@!" << endl;
			// cout << sz << ' ' << z << "#@!!#" << endl;
			if(x <= z) cout << ask(rt, z - x + 1) + ans * c << '\n';
			else cout << ask(rt, sz - (x - z) + 1) + (ans - 1) * c << '\n';
		}
	}
	return cerr << endl << 1.0 * clock() / CLOCKS_PER_SEC << endl, 0;
}