rt 这次真的调疯了（整整一天），挂在这，求求了

//域值分块——分块里套分块
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mxn=265;
int n,m,mx,k[N],id[N],sum[N],sz[mxn<<2][mxn+5],nm[mxn<<2][N+5];
int ans,cnt[N],cur[N],L[N],R[N],ln;
char op[5];
int ma(int x,int y){return x>y?x:y;}
struct node
{
	int a[1000],sze[1000],num[N];
	int p,e,len;
}c[mxn];
void innt()
{
	id[0]=1,L[1]=0;
	for(int i=1;i<=100000;i++)
	{
		id[i]=(i-1)/mxn+1;
		if(id[i]!=id[i-1])
			L[id[i]]=i,R[id[i-1]]=i-1;
	}
	R[id[100000]]=N-10;
}
void chg(int x,int y)
{
	int l=x-sum[k[x]],o=c[k[x]].a[l];
	c[k[x]].num[o]--,c[k[x]].sze[id[o]]--;
	c[k[x]].num[y]++,c[k[x]].sze[id[y]]++;
	c[k[x]].a[l]=y;
	for(int i=k[x];i;i=c[i].e)
	{
		sz[i][id[o]]--,sz[i][id[y]]++;
		nm[i][o]--,nm[i][y]++;
		//printf("%d %dK",sz[i][id[y]],nm[i][y]);
	}
}
int Ak(int z)
{
	for(int i=1;i<=id[mx];i++)
	{
		if(z<=cur[i])
		{
			for(int j=L[i];j<=R[i];j++)
			{
				if(cnt[j]>=z)
					return j;
				z-=cnt[j];
			}
		}
		else 
			z-=cur[i];
	}
	return 0;
}
void bx(int l,int r,int o)
{
	for(int i=l;i<=r;i++)
	{
		int v=c[k[i]].a[i-sum[k[i]]];
		cnt[v]+=o,cur[id[v]]+=o;
	}
}
int ak(int x,int y,int z)
{
	int o,f;
	if(k[x]==k[y])
	{
		bx(x,y,1);
		o=Ak(z);
		bx(x,y,-1);
		return o;
	}
	bx(x,sum[c[k[x]].e],1),bx(sum[k[y]]+1,y,1);
	for(int i=1;i<=id[mx];i++)
	{
		f=cur[i]+sz[c[k[y]].p][i]-sz[k[x]][i];
		//printf("Y%d %d %d %d\n",z,f,sz[c[k[y]].p][i],sz[k[x]][i]);
		if(z<=f)
		{
			for(int j=L[i];j<=R[i];j++)
			{
				int g=cnt[j]+nm[c[k[y]].p][j]-nm[k[x]][j];
				//printf("%d ",g);
				if(g>=z)
				{
					bx(x,sum[c[k[x]].e],-1),bx(sum[k[y]]+1,y,-1);
					return j;
				}
				z-=g;
			}
		}
		else 
			z-=f;		
	}
	return 0;
}
void prt(int x)
{
	c[++ln].p=x,c[ln].e=c[x].e,c[x].e=ln,c[c[ln].e].p=ln;
	for(int i=mxn+1;i<=c[x].len;i++)
	{
		c[ln].a[++c[ln].len]=c[x].a[i];
		c[ln].sze[id[c[x].a[i]]]++,c[ln].num[c[x].a[i]]++;
		c[x].sze[id[c[x].a[i]]]--,c[x].num[c[x].a[i]]--;
	}
	c[x].len=mxn;
	sum[ln]=sum[x]+c[x].len;
	for(int i=sum[ln]+1;i<=sum[ln]+c[ln].len;i++)
		k[i]=ln;
	for(int i=1;i<=id[mx];i++)
		sz[x][i]=sz[c[x].p][i]+c[x].sze[i],sz[ln][i]=sz[x][i]+c[ln].sze[i];
	for(int i=1;i<=mx;i++)
		nm[x][i]=nm[c[x].p][i]+c[x].num[i],nm[ln][i]=nm[x][i]+c[ln].num[i];
}
void ins(int x,int y)
{
	int l=x-sum[k[x]];
	c[k[x]].len++,c[k[x]].sze[id[y]]++,c[k[x]].num[y]++;
	for(int i=c[k[x]].len;i>=l+2;i--)
		c[k[x]].a[i]=c[k[x]].a[i-1];
	c[k[x]].a[x+1]=y;
	for(int i=c[k[x]].e;i;i=c[i].e)
	{
		sum[i]++,sz[i][id[y]]++,nm[i][y]++;
		k[sum[i]+1]=i,k[sum[i]+c[i].len]=i;
	}
	k[sum[k[x]]+c[k[x]].len]=k[x],sz[k[x]][id[y]]++,nm[k[x]][y]++;
	if(c[k[x]].len>=2*mxn)
		prt(k[x]);
}
int main()
{
	innt();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		k[i]=(i-1)/mxn+1;
	for(int i=1;i<=k[n];i++)
		c[i].p=i-1,c[i].e=i+1;
	k[0]=1,c[k[n]].e=0,ln=k[n];
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		mx=ma(x,mx);
		c[k[i]].a[++c[k[i]].len]=x;
		c[k[i]].num[x]++,c[k[i]].sze[id[x]]++;
	}
	for(int i=1;i<=k[n];i++)
	{
		sum[i]=sum[i-1]+c[i-1].len;
		for(int j=1;j<=id[mx];j++)
			sz[i][j]=sz[i-1][j]+c[i].sze[j];
		for(int j=1;j<=mx;j++)
			nm[i][j]=nm[i-1][j]+c[i].num[j];
	}
	scanf("%d",&m);
	while(m--)
	{
		scanf("%s",op);
		if(op[0]=='Q')
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			x^=ans,y^=ans,z^=ans;
			printf("%d\n",ans=ak(x,y,z));
		}
		else if(op[0]=='M')
		{
			int x,y;
			scanf("%d%d",&x,&y);
			x^=ans,y^=ans;
			mx=ma(mx,y);
			chg(x,y);
		}
		else if(op[0]=='I')
		{
			int x,y;
			scanf("%d%d",&x,&y);
			x^=ans,y^=ans;
			mx=ma(y,mx),ins(x-1,y);
		}
	}
    return 0;
}