#include <bits/stdc++.h>

using namespace std;

const int nTr=1000005, nSg=15000005, alphaA=4, alphaB=5;

int STop;

struct Seg *Snull;

struct Seg { Seg *l, *r; int s, cnt; }Sg[nSg], *iSg=Sg, *bin[nSg];

Seg *newS() {

	Seg *x;

	if(!STop) x=iSg++;

	else x=bin[STop--];

	x->l=x->r=Snull; x->s=0; x->cnt=1;

	return x;

}

void clean(Seg *&x) {

	if(x!=Snull && (--x->cnt==0)) {

		bin[++STop]=x;

		clean(x->l); clean(x->r);

	}

	x=Snull;

}

Seg *merge(Seg *l, Seg *r) {

	if(l==Snull) { ++r->cnt; return r; }

	if(r==Snull) { ++l->cnt; return l; }

	Seg *p=newS();

	p->l=merge(l->l, r->l);

	p->r=merge(l->r, r->r);

	p->s=l->s+r->s;

	return p;

}

Seg *ins(Seg *p, int k, int _s, int l, int r) {

	if(p->s+_s==0) { ++Snull->cnt; return Snull; }

	int mid=(l+r)>>1;

	Seg *x=newS();

	x->l=p->l; ++x->l->cnt;

	x->r=p->r; ++x->r->cnt;

	x->s=p->s+_s;

	if(l==r) return x;

	if(k<=mid) { --x->l->cnt; x->l=ins(p->l, k, _s, l, mid); }

	else { --x->r->cnt; x->r=ins(p->r, k, _s, mid+1, r); }

	return x;

}

Seg *ins(Seg *p, int k, int s) {

	Seg *x=ins(p, k, s, 0, 70000);

	clean(p);

	return x;

}

struct node *null;

struct node {

	node *c[2];

	int s, k;

	Seg *t;

	void pushup() { s=c[0]->s+c[1]->s+1; t=ins(merge(c[0]->t, c[1]->t), k, 1); }

}Tr[nTr], *iTr=Tr, *root;

node* newT(int k) {

	node *x=iTr++;

	x->s=1; x->k=k; x->c[0]=x->c[1]=null; x->t=Snull; ++Snull->cnt;

	return x;

}

node* flatten(node *x, node *y) {

	if(x==null) return y;

	clean(x->t);

	x->c[1]=flatten(x->c[1], y);

	return flatten(x->c[0], x);

}

node* build(node *x, int n) {

	if(n==0) { x->c[0]=null; return x; }

	node *y=build(x, n>>1);

	node *z=build(y->c[1], n-(n>>1)-1);

	y->c[1]=z->c[0];

	z->c[0]=y;

	y->pushup();

	return z;

}

void rebuild(node *&x) {

	static node y;

	node *head=flatten(x, &y);

	build(head, x->s);

	x=y.c[0];

}

node *rB;

void insert(node *&x, int pos, int val) {

	if(x==null) { x=newT(val); x->t=ins(Snull, val, 1); return; }

	++x->s;

	x->t=ins(x->t, val, 1);

	int s=x->c[0]->s;

	if(pos<=s) insert(x->c[0], pos, val);

	else insert(x->c[1], pos-s-1, val);

	if(max(x->c[0]->s, x->c[1]->s)*alphaB<=x->s*alphaA) { if(rB!=null) rebuild(x->c[rB==x->c[1]]), rB=null; }

	else rB=x;

}

int update(node *x, int pos, int val) {

	x->t=ins(x->t, val, 1);

	int s=x->c[0]->s+1;

	if(pos==s) swap(val, x->k);

	else if(pos<s) val=update(x->c[0], pos, val);

	else val=update(x->c[1], pos-s, val);

	x->t=ins(x->t, val, -1);

	return val;

}

struct Link {

	int len;

	struct Ln { int l, r; Seg *t; }val[nTr<<2];

	void add(Seg *x) { if(x==Snull) return; ++len; val[len].t=x; val[len].l=len-1; val[len].r=0; val[len-1].r=len; }

	void del(int x) { val[val[x].l].r=val[x].r; val[val[x].r].l=val[x].l; }

	void clr() { len=0; val[0].l=val[0].r=0; }

};

void query(node *x, int R, Link &a, Link &b) {

	if(x==null || !R) return;

	int s=x->c[0]->s+1;

	if(s<=R) a.add(x->t), b.add(x->c[1]->t), query(x->c[1], R-s, a, b);

	else query(x->c[0], R, a, b);

}

int last;

Link a, b;

void Query(int x, int y, int k) {

	a.clr(); b.clr();

	query(root, x-1, b, a);

	query(root, y, a, b);

	int l=0, r=70000;

	while(l<r) {

		x=a.val[0].r, y=b.val[0].r;

		int sum=0;

		while(x) sum+=a.val[x].t->l->s, x=a.val[x].r;

		while(y) sum-=b.val[y].t->l->s, y=b.val[y].r;

		x=a.val[0].r, y=b.val[0].r;

		if(k<=sum) {

			r=(l+r)>>1;

			while(x) { a.val[x].t=a.val[x].t->l; if(a.val[x].t==Snull) a.del(x); x=a.val[x].r; }

			while(y) { b.val[y].t=b.val[y].t->l; if(b.val[y].t==Snull) b.del(y); y=b.val[y].r; }

		}

		else {

			l=((l+r)>>1)+1;

			k-=sum;

			while(x) { a.val[x].t=a.val[x].t->r; if(a.val[x].t==Snull) a.del(x); x=a.val[x].r; }

			while(y) { b.val[y].t=b.val[y].t->r; if(b.val[y].t==Snull) b.del(y); y=b.val[y].r; }

		}

	}

	printf("%d\n", last=l);

}

void Update(int x, int val) {

	update(root, x, val);

}

void Insert(int x, int val) {

	rB=null;

	insert(root, x, val);

	if(rB!=null) rebuild(root);

}

void build(node *&x, int l, int r) {

	if(l>r) return;

	int mid=(l+r)>>1;

	x=newT(-1);

	build(x->c[0], l, mid-1);

	scanf("%d", &x->k);

	build(x->c[1], mid+1, r);

	x->pushup();

}

void init() {

	Snull=new Seg; Snull->l=Snull->r=Snull; Snull->s=0;

	null=new node; null->s=null->k=0; null->t=Snull; null->c[0]=null->c[1]=null;

	root=null;

}

int main() {

	init();

	int n, x, y, k; scanf("%d", &n);

	build(root, 1, n);

	scanf("%d", &n);

	char s[5];

	while(n--) {

		scanf("%s", s); scanf("%d%d", &x, &y); x^=last, y^=last;

		if(s[0]=='Q') scanf("%d", &k), k^=last, Query(x, y, k);

		else if(s[0]=='M') Update(x, y);

		else Insert(x-1, y);

	}

	return 0;

}