#include <bits/stdc++.h>
using namespace std;

const int N = 4e5;
int a[N];
int root, tot = 2e5;
int n, m;

struct node {
    int l, r;
    int key;
    int book;
    int pri; // 大根堆
    int siz;
}t[N];

int newNode(int v, int b) {
    ++tot;
    t[tot].key = v;
    t[tot].book = b;
    t[tot].pri = rand();
    t[tot].siz = 1;
    return tot;
}

void update(int p) {
    t[p].siz = t[t[p].l].siz + t[t[p].r].siz + 1;
}

void split(int p, int v, int &L, int &R) {
    if (!p) { L=R=0; return; }
    if (t[p].key <= v) {
        L = p;
        split(t[p].r, v, t[p].r, R);
    } else {
        R = p;
        split(t[p].l, v, L, t[p].l);
    }
    update(p);
}

int merge(int L, int R) {
    if (!L || !R) return L+R;
    if (t[L].pri > t[R].pri) {
        t[L].r = merge(t[L].r, R);
        update(L); return L;
    } else {
        t[R].l = merge(L, t[R].l); // 注意，merge的顺序不能交换
        update(R); return R;
    }
}

void insert(int v, int b) { // 位置，书
    int x, y, z;
    split(root, v, x, z);
    y = newNode(v, b);
    root = merge(merge(x, y), z);
} 

void del(int v) {
    int x, y, z;
    split(root, v, x, z);
    split(x, v-1, x, y); // 
    y = merge(t[y].l, t[y].r);
    root = merge(merge(x, y), z);
}

int rnk(int v) {
    int x, y;
    split(root, v-1, x, y);
    int ret = t[x].siz+1;
    root = merge(x, y);
    return ret;
}

int kth(int p, int k) {
    if (k == t[t[p].l].siz + 1) return p;
    if (k < t[t[p].l].siz + 1) return kth(t[p].l, k);
    else return kth(t[p].r, k-t[t[p].l].siz-1);
}

int getPre(int v) {
    int x, y;
    split(root, v-1, x, y);
    int ret = kth(x, t[x].siz);
    root = merge(x, y);
    return ret;
}

int getSuc(int v) {
    int x, y;
    split(root, v, x, y);
    int ret = kth(y, 1);
    root = merge(x, y);
    return ret;
}

void pt(int x) {
    printf("%d\n", x);
}

int main() {
    srand(time(NULL));
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; ++i) {
        int x; scanf("%d", &x);
        insert(i, x);
        a[x] = tot;
    }
    while (m--) {
        char op[10]; int s, pos, x;
        scanf("%s%d", op, &s);
        switch (op[0]) {
            case 'T': 
                pos = t[kth(root, 1)].key - 1;
                del(t[a[s]].key);
                insert(pos, s);
                a[s] = tot;
                break;
            case 'B':
                pos = t[kth(root, n)].key + 1;
                del(t[a[s]].key);
                insert(pos, s);
                a[s] = tot;
                break;
            case 'I':
                scanf("%d", &x);
                if (x == -1) {
                    int pre = getPre(t[a[s]].key);
                    swap(t[a[s]].book, t[pre].book);
                    a[s] = pre;
                } 
                if (x == 1) {
                    int suc = getSuc(t[a[s]].key);
                    swap(t[a[s]].book, t[suc].book);
                    a[s] = suc;
                }
                break;
            case 'A':
                pt(rnk(t[a[s]].key)-1);
                break;
            case 'Q':
                pt(t[kth(root, s)].book);
                break;
        }
    }
    return 0;
}