这道题显然平衡树，splay，treap什么的随便切
然而我不想打，决定水过这道题
把空间开3倍，树状数组维护它前面的树的个数，开个id数组记录位置
找一个数排名直接二分加求前缀和，log^2的搞一搞
把一个数放在顶/低 直接丢在当前顶/低的前后就可以了不然开3倍数组干嘛
c常数小堪比log的平衡树居然还快一些

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int _(3e5 + 10), INF(2e9), PF(1e5);

IL ll Read(){

    char c = '%'; ll x = 0, z = 1;

    for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';

    return x * z;

}

int n, m, t[_], id[_], a[_];

char opt[10];

IL void Add(RG int x, RG int v){  for(; x <= PF * 3; x += x & -x) t[x] += v;  }

IL int Query(RG int x){  RG int cnt = 0; for(; x; x -= x & -x) cnt += t[x]; return cnt;  }

IL int Find(RG int x){

    RG int l = 1, r = PF * 3;

    while(l < r){

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

        if(Query(mid) >= x) r = mid;

        else l = mid + 1;

    }

    return l;

}

int main(RG int argc, RG char *argv[]){

    n = Read(); m = Read();

    for(RG int i = 1; i <= n; ++i) a[PF + i] = Read(), Add(PF + i, 1), id[a[PF + i]] = PF + i;

    while(m--){

        scanf(" %s", opt); RG int x = Read(), y, p, q;

        if(opt[0] == 'T'){

            p = Find(1);

            a[id[x]] = 0; Add(id[x], -1);

            id[x] = p - 1;

            a[id[x]] = x; Add(id[x], 1);

        }

        else if(opt[0] == 'B'){

            p = Find(n);

            a[id[x]] = 0; Add(id[x], -1);

            id[x] = p + 1;

            a[id[x]] = x; Add(id[x], 1);

        }

        else if(opt[0] == 'I'){

            y = Read(); q = Query(id[x]);

            p = Find(q + y); RG int t = a[p];

            swap(a[p], a[id[x]]); swap(id[x], id[t]);

        }

        else if(opt[0] == 'A') printf("%d\n", Query(id[x]) - 1);

        else printf("%d\n", a[Find(x)]);

    }

    return 0;

}