#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define y1 skldjfskldjg

#define y2 skldfjsklejg

using namespace std;

const int N = 4e5 + ;

const int M = 5e5 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = ;

const int B = 1e5;

int val[N], hs[N], n, m;

char s[];

struct node {

    node* ch[];

    int key, fix, sz, cnt;

    void update() {

        sz = ch[]->sz + ch[]->sz + cnt;

    }

};

typedef node* P_node;

struct Treap {

    node base[N], nil;

    P_node root, null, len;

    Treap() {

        root = null = &nil;

        null->key = null->fix = 1e9;

        null->sz = null->cnt = ;

        null->ch[] = null->ch[] = null;

        len = base;

    }

    P_node newnode(int tkey) {

        len->key = tkey;

        len->fix = rand();

        len->ch[] = len->ch[] = null;

        len->sz = len->cnt = ;

        return len++;

    }

    void rot(P_node &p, int d) {

        P_node k = p->ch[d ^ ];

        p->ch[d ^ ] = k->ch[d];

        k->ch[d] = p;

        p->update();

        k->update();

        p = k;

    }

    void _Insert(P_node &p, int tkey) {

        if(p == null) {

            p = newnode(tkey);

        } else if(p->key == tkey) {

            p->cnt++;

        } else {

            int d = tkey > p->key;

            _Insert(p->ch[d], tkey);

            if(p->ch[d]->fix > p->fix) {

                rot(p, d ^ );

            }

        }

        p->update();

    }

    void _Delete(P_node &p, int tkey) {

        if(p == null) return;

        if(p->key == tkey) {

            if(p->cnt > ) p->cnt--;

            else if(p->ch[] == null) p = p->ch[];

            else if(p->ch[] == null) p = p->ch[];

            else {

                int d = p->ch[]->fix > p->ch[]->fix;

                rot(p, d);

                _Delete(p->ch[d], tkey);

            }

        } else {

            _Delete(p->ch[tkey > p->key], tkey);

        }

        p->update();

    }

    int _Kth(P_node p, int k) {

        if(p == null || k <  || k > p->sz) return ;

        if(k < p->ch[]->sz + ) return _Kth(p->ch[], k);

        if(k > p->ch[]->sz + p->cnt) return _Kth(p->ch[], k - p->ch[]->sz - p->cnt);

        return p->key;

    }

    int _Rank(P_node p, int tkey, int res) {

        if(p == null) return -;

        if(p->key == tkey) return p->ch[]->sz + res + ;

        if(tkey < p->key) return _Rank(p->ch[], tkey, res);

        return _Rank(p->ch[], tkey, res + p->ch[]->sz + p->cnt);

    }

    int _Pred(P_node p, int tkey){

        if(p == null) return -1e9;

        if(tkey <= p->key) return _Pred(p->ch[], tkey);

        return max(p->key, _Pred(p->ch[], tkey));

    }

    int _Succ(P_node p, int tkey){

        if(p == null) return 1e9;

        if(tkey >= p->key) return _Succ(p->ch[], tkey);

        return min(p->key, _Succ(p->ch[], tkey));

    }

    void Insert(int tkey){ _Insert(root,tkey); }

    void Delete(int tkey){ _Delete(root,tkey); }

    int Kth(int k){ return _Kth(root,k); }

    int Rank(int tkey){ return _Rank(root,tkey,); }

    int Pred(int tkey){ return _Pred(root,tkey); }

    int Succ(int tkey){ return _Succ(root,tkey); }

}tp;

int main() {

    scanf("%d%d", &n, &m);

    int mx = n + B, mn =  + B;

    for(int i = ; i <= n; i++) {

        int x; scanf("%d", &x);

        val[x] = i + B;

        hs[i + B] = x;

        tp.Insert(i + B);

    }

    while(m--) {

        int id, t;

        scanf("%s", s);

        if(s[] == 'T') {

            scanf("%d", &id);

            tp.Delete(val[id]);

            val[id] = --mn;

            hs[mn] = id;

            tp.Insert(val[id]);

        } else if(s[] == 'B') {

            scanf("%d", &id);

            tp.Delete(val[id]);

            val[id] = ++mx;

            hs[mx] = id;

            tp.Insert(val[id]);

        } else if(s[] == 'I') {

            scanf("%d%d", &id, &t);

            if(t == ) {

                int z = tp.Succ(val[id]);

                if(z < - || z > ) continue;

                int id2 = hs[z], v = val[id];

                swap(val[id], val[id2]);

                swap(hs[v], hs[z]);

            } else if(t == -) {

                int z = tp.Pred(val[id]);

                if(z < - || z > ) continue;

                int id2 = hs[z], v = val[id];

                swap(val[id], val[id2]);

                swap(hs[v], hs[z]);

            }

        } else if(s[] == 'A'){

            scanf("%d", &id);

            printf("%d\n", tp.Rank(val[id]) - );

        } else {

            scanf("%d", &id);

            printf("%d\n", hs[tp.Kth(id)]);

        }

    }

    return ;

}