#include <bits/stdc++.h>

using namespace std;

#define pii pair <int, int> 
#define fi first
#define se second

const int mod = 998244353;

const int N = 70000;
const int M = 20000005;

struct Segment_Tree {
	struct tree {
		int ls, rs;
		int sum;
	} t[M];
	
	void init(int x) {
		t[x].ls = t[x].rs = t[x].sum = 0;
	}
	
	void pushup(int p) {
		t[p].sum = t[t[p].ls].sum + t[t[p].rs].sum;
	}
	
	int stk[M], top;
	
	int addnew() {
		init(stk[top]);
		return stk[top--];
	}
	
	void update(int &p, int l, int r, int x, int v) {
		if (!p) p = addnew();
		if (l == r) {
			t[p].sum += v;
			return ;
		}
		int mid = (l + r) / 2;
		if (x <= mid) update(t[p].ls, l, mid, x, v);
		else update(t[p].rs, mid + 1, r, x, v);
		pushup(p);
		return ;
	}
	
	void merge(int &x, int y) {
		if (!y) return ;
		if (!x) x = addnew();
		t[x].sum += t[y].sum;
		merge(t[x].ls, t[y].ls);
		merge(t[x].rs, t[y].rs);
	}
	
	void clear(int &x) {
		if (!x) return ;
		stk[++top] = x;
		if (t[x].ls) clear(t[x].ls);
		if (t[x].rs) clear(t[x].rs);
		init(x);
		x = 0;
	}
	
	int query(int p, int l, int r, int k) {
		if (l == r) return l;
		int mid = (l + r) / 2, sum = t[p].sum - t[t[p].rs].sum;
		//cout << l << ' ' << r << ' ' << sum << endl;
		if (sum < k) return query(t[p].rs, mid + 1, r, k - sum);
		else return query(t[p].ls, l, mid, k);
	}
} T;

struct Fhq_Treap {
	struct Tree {
		int ls, rs;
		int key;
		int root;
		int val;
		int siz;
	} t[M];
	
	int stk[M], top;
	
	void pushup(int p) {
		T.clear(t[p].root);
		if (t[p].ls) T.merge(t[p].root, t[t[p].ls].root);
		if (t[p].rs) T.merge(t[p].root, t[t[p].rs].root);
		T.update(t[p].root, 0, N, t[p].key, 1);	
		t[p].siz = t[t[p].ls].siz + t[t[p].rs].siz + 1; 
	}
	
	pii split(int p, int k) {
		if (!p) return {0, 0};
		if (t[t[p].ls].siz + 1 <= k) {
			pii tp = split(t[p].rs, k - (t[t[p].ls].siz + 1));
			t[p].rs = tp.fi;
			pushup(p);
			return {p, tp.se};
		} else {
			pii tp = split(t[p].ls, k);
			t[p].ls = tp.se;
			pushup(p);
			return {tp.fi, p};
		}
	}
	
	int merge(int u, int v) {
		if (!u || !v) return u + v;
		if (t[u].val < t[v].val) {
			t[u].rs = merge(t[u].rs, v);
			pushup(u);
			return u;
		} else {
			t[v].ls = merge(u, t[v].ls);
			pushup(v);
			return v;
		}
	}
	
	int addnew(int x) {
		t[stk[top]].key = x;
		t[stk[top]].ls = t[stk[top]].rs = 0;
		t[stk[top]].siz = 1;
		T.update(t[stk[top]].root, 0, N, x, 1);
		t[stk[top]].val = 1ll * rand() * rand() % mod * rand() % mod;
		return stk[top--];
	}
	
	void clear(int &p) {
		if (!p) return ;
		t[p].siz = 0;
		T.clear(t[p].root);
		t[p].ls = t[p].rs = 0;
		t[p].key = t[p].val = 0;
		if (t[p].ls) clear(t[p].ls);
		if (t[p].rs) clear(t[p].rs);
		p = 0;
	}
	
	void inorder(int p) {
		if (!p) return ;
		inorder(t[p].ls);
		cout << t[p].key << ' ';
		inorder(t[p].rs);
	}	
	
} FHQ;

int n, q;
char s[10];

int rt;

signed main() {
	scanf("%d", &n);
	for (int i = 1; i <= M - 5; i++) T.stk[++T.top] = i;
	for (int i = 1; i <= N + 5; i++) FHQ.stk[++FHQ.top] = i;
	srand(time(0));
	for (int i = 1, x; i <= n; i++) {
		scanf("%d", &x);
		rt = FHQ.merge(rt, FHQ.addnew(x));
	}	 
	scanf("%d", &q);
	int lst = 0;
	while (q--) {
		scanf("%s", s);
		if (s[0] == 'M') {
			int x, val;
			scanf("%d %d", &x, &val);
			x ^= lst, val ^= lst;
			pii tp = FHQ.split(rt, x);
			pii qwq = FHQ.split(tp.fi, x - 1);
			int y = FHQ.t[qwq.se].key;
			FHQ.clear(qwq.se);
			rt = FHQ.merge(qwq.fi, FHQ.merge(FHQ.addnew(val), tp.se));
		} else if (s[0] == 'I') {
			int x, val;
			scanf("%d %d", &x, &val);
			x ^= lst, val ^= lst;			
			pii tp = FHQ.split(rt, x);
			pii qwq = FHQ.split(tp.fi, x - 1);
			rt = FHQ.merge(qwq.fi, FHQ.merge(FHQ.addnew(val), FHQ.merge(qwq.se, tp.se)));			
		} else {
			int x, y, k;
			scanf("%d %d %d", &x, &y, &k);
			x ^= lst, y ^= lst, k ^= lst;			
			pii tp = FHQ.split(rt, y);
			pii qwq = FHQ.split(tp.fi, x - 1);
			printf("%d\n", lst = T.query(FHQ.t[qwq.se].root, 0, N, k));
			rt = FHQ.merge(qwq.fi, FHQ.merge(qwq.se, tp.se));						
		}
		//FHQ.inorder(rt);
		//puts("");
		//printf("%d\n", T.query(FHQ.t[rt].root, 0, N, 3));
	}
	return 0;
} 

rt，fhq套线段树，正确性已验证，但是为什么后四个点都过不去(TLE)