#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<vector>

#define alpha 0.75

#define N 10000005

int read(){

    char ch=getchar();int t=,f=;

    while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

    while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

    return t*f;

}

int tmp;

int n,m,sz,ans,root;

int v[],dfn[],rt[],ls[],rs[];

struct seg{int l,r,sum;}a[N];

std::vector<int>p,t,rec;

int newnode(){

    if (!rec.size()) return ++sz;

    else{

        int k=rec.back();rec.pop_back();

        return k;

    }

}

void recliam(int &x){

    if (!x) return;

    rec.push_back(x);

    recliam(a[x].l);recliam(a[x].r);

    a[x].sum=;x=;

}

void insert(int &k,int l,int r,int val,int f){

    if (!k) k=newnode();

    if (l==r){a[k].sum+=f;return;}

    int mid=(l+r)>>;

    if (val<=mid) insert(a[k].l,l,mid,val,f);

    else insert(a[k].r,mid+,r,val,f);

    a[k].sum=a[a[k].l].sum+a[a[k].r].sum;

    if (!a[k].sum) recliam(k);

}

void build(int &k,int l,int r){

    int mid=(l+r)>>;

    if (l>r) return;

    if (l==r){

        k=dfn[l];insert(rt[k],,,v[k],);return;

    }

    k=dfn[mid];

    build(ls[k],l,mid-);build(rs[k],mid+,r);

    for (int i=l;i<=r;i++)

     insert(rt[k],,,v[dfn[i]],);

}

void del(int &x){

    if (!x) return;recliam(rt[x]);

    del(ls[x]);p.push_back(x);del(rs[x]);

    x=;

}

void rebuild(int &x){

    del(x);int s1=p.size();

    for (int i=;i<=s1;i++) dfn[i]=p[i-];

    build(x,,s1);

    p.clear();

}

int modify(int k,int x,int val){

    insert(rt[k],,,val,);

    int t,L=a[rt[ls[k]]].sum;

    if (L+==x){t=v[k];v[k]=val;}

    else if (L>=x) t=modify(ls[k],x,val);

    else t=modify(rs[k],x-L-,val);

    insert(rt[k],,,t,-);

    return t;

}

void query(int k,int l,int r){

    int L=a[rt[ls[k]]].sum,R=a[rt[k]].sum;

    if (l==&&r==R){t.push_back(rt[k]);return;}

    if (l<=L+&&r>=L+)p.push_back(v[k]);

    if (r<=L)query(ls[k],l,r);

    else if (l>L+) query(rs[k],l-L-,r-L-);

    else{

        if (l<=L) query(ls[k],l,L);

        if (R>L+) query(rs[k],,r-L-);

    }

}

int solve_query(int L,int R,int K){

    query(root,L,R);K--;

    int l=,r=,s1=t.size(),s2=p.size();

    while (l<r){

        int mid=(l+r)>>,sum=;

        for (int i=;i<s1;i++) sum+=a[a[t[i]].l].sum;

        for (int i=;i<s2;i++)

         if (p[i]>=l&&p[i]<=mid) sum++;

        if (K<sum){

            for (int i=;i<s1;i++) t[i]=a[t[i]].l;

            r=mid;

        } else{

            for (int i=;i<s1;i++) t[i]=a[t[i]].r;

            l=mid+;K-=sum;

        }

    }

    t.clear();p.clear();

    return l;

}

void insert(int &k,int x,int val){

    if (!k){

        k=++n;

        insert(rt[k],,,val,);

        v[k]=val;

        return;

    }

    insert(rt[k],,,val,);

    int L=a[rt[ls[k]]].sum;

    if (L>=x) insert(ls[k],x,val);else insert(rs[k],x-L-,val);

    if (a[rt[k]].sum*alpha>std::max((double)a[rt[ls[k]]].sum,(double)a[rt[rs[k]]].sum)){

        if (tmp){

            if (ls[k]==tmp) rebuild(ls[k]);

            else rebuild(rs[k]);

            tmp=;

        }

    }else tmp=k;

}

int main(){

    n=read();

    for (int i=;i<=n;i++) v[i]=read();

    for (int i=;i<=n;i++) dfn[i]=i;

    build(root,,n);

    m=read();

    char ch[];int x,y,K;

    while (m--){

        scanf("%s",ch);

        x=read();y=read();x^=ans;y^=ans;

        switch(ch[]){

            case 'Q':K=read();K^=ans;ans=solve_query(x,y,K);printf("%d\n",ans);break;

            case 'M':modify(root,x,y);break;

            case 'I':tmp=;insert(root,x-,y);if (tmp){tmp=;rebuild(root);}break;

        }

    }

}