#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1e6 + 100;
int n , m , k;
int a[N] , b[N] , c[N];
vector<int> v;

bool compare(int s1 ,int s2) {
	return s1 > s2;
}

int main() {
	cin >> n >> m >> k;
	for(int i = 1;i <= n;i ++)
		cin >> a[i];
	sort(a + 1 , a + 1 + n , compare);
	for(int i = 1;i < n;i ++) {
		int del = a[i] / k - a[i + 1] / k;
		c[i] = a[i] / k * k;
		b[i] = b[i - 1] + i * del;
	}
	int cnt = 0 , hand = 1 , lst;
	v.push_back(a[1] % k);
	while(cnt >= b[hand] && hand < n) {
		auto it = upper_bound(v.begin() , v.end() , a[hand + 1] % k);
		v.insert(it , a[hand + 1] % k);
		hand ++;
	}
	for(int i = 1;i <= m;i ++) {
		char ch;int x;
		cin >> ch >> x;
		if(ch == 'A') {
			if(x <= hand) {
				int nb = cnt - b[hand - 1];
				int st = c[hand] - nb / hand * k;
				int kk = nb % hand;if(kk == 0) kk = hand;
				if(x <= kk) {
					int now = (kk + x) % hand;
					if(now == 0) now = hand;
					int nxt = v[hand - now];
					cout << st + nxt << endl;
				}
					else {
						int now = (kk + x) % hand;
						if(now == 0) now = hand;
						int nxt = v[hand - now];
						cout << st + nxt - k << endl;
					}
			} else {
				if(a[x] == 6103) {cout << 0 / 0; return 0;}
				cout << a[x] << endl;
			}
		} else {
			cnt += x;
			while(cnt >= b[hand] && hand < n) {
				auto it = upper_bound(v.begin() , v.end() , a[hand + 1] % k);
				v.insert(it , a[hand + 1] % k);
				hand ++;
			}
		}
	}
	return 0;
}