小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。 当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。 久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。

第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书放在最上面。 2． Bottom S——表示把编号为S的书放在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。

对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。

Query

Top

Ask

Bottom

Ask

Top

Insert  -

Query

Query

Ask 

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 80010

struct Node {

	int siz;

	Node() {}

} ns[maxn];

int ToT, fa[maxn], ch[2][maxn], id[maxn];

void maintain(int o) {

	ns[o].siz = 1;

	for(int i = 0; i < 2; i++) if(ch[i][o])

		ns[o].siz += ns[ch[i][o]].siz;

	return ;

}

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

	if(l > r) return ;

	int mid = l + r >> 1; o = id[mid];

	build(ch[0][o], l, mid - 1); build(ch[1][o], mid + 1, r);

	if(ch[0][o]) fa[ch[0][o]] = o;

	if(ch[1][o]) fa[ch[1][o]] = o;

	return maintain(o);

}

void rotate(int u) {

	int y = fa[u], z = fa[y], l = 0, r = 1;

	if(z) ch[ch[1][z]==y][z] = u;

	if(ch[1][y] == u) swap(l, r);

	fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;

	ch[l][y] = ch[r][u]; ch[r][u] = y;

	maintain(y); maintain(u);

	return ;

}

void splay(int u) {

	while(fa[u]) {

		int y = fa[u], z = fa[y];

		if(z) {

			if(ch[0][y] == u ^ ch[0][z] == y) rotate(u);

			else rotate(y);

		}

		rotate(u);

	}

	return ;

}

int splitl(int u) {

	splay(u);

	int tmp = ch[0][u];

	fa[tmp] = ch[0][u] = 0;

	maintain(u);

	return tmp;

}

int splitr(int u) {

	splay(u);

	int tmp = ch[1][u];

	fa[tmp] = ch[1][u] = 0;

	maintain(u);

	return tmp;

}

int merge(int a, int b) {

	if(!a) return maintain(b), b;

	if(!b) return maintain(a), a;

	while(ch[1][a]) a = ch[1][a];

	splay(a);

	ch[1][a] = b; fa[b] = a;

	return maintain(a), a;

}

int getrt() {

	int u = 1; while(fa[u]) u = fa[u];

	return u;

}

int Find(int o, int k) {

	if(!o) return 0;

	int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;

	if(k == ls + 1) return o;

	if(k > ls + 1) return Find(ch[1][o], k - ls - 1);

	return Find(ch[0][o], k);

}

int main() {

	int n = read(), q = read();

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

	int tmp = 0; build(tmp, 1, n);

	int tq = q;

	while(q--) {

		char cmd[10]; scanf("%s", cmd);

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

			int mrt = read(), lrt = splitl(mrt), rrt = splitr(mrt);

			lrt = merge(lrt, rrt); merge(mrt, lrt);

		}

		if(cmd[0] == 'B') {

			int mrt = read(), lrt = splitl(mrt), rrt = splitr(mrt);

			lrt = merge(lrt, rrt); merge(lrt, mrt);

		}

		if(cmd[0] == 'I') {

			int mrt = read(), t = read(), rk, lrt, rrt;

			if(!t) continue;

			splay(mrt); rk = (ch[0][mrt] ? ns[ch[0][mrt]].siz : 0) + 1 + t;

			if(rk < 1 || rk > n) continue; rk = Find(getrt(), rk);

			if(t < 0) {

				lrt = splitl(rk); splitl(mrt); rrt = splitr(mrt);

				lrt = merge(lrt, mrt); lrt = merge(lrt, rk); merge(lrt, rrt);

			}

			else {

				lrt = splitl(mrt); splitl(rk); rrt = splitr(rk);

				lrt = merge(lrt, rk); lrt = merge(lrt, mrt); merge(lrt, rrt);

			}

		}

		if(cmd[0] == 'A') {

			int u = read();

			splay(u);

			printf("%d\n", ch[0][u] ? ns[ch[0][u]].siz : 0);

		}

		if(cmd[0] == 'Q') printf("%d\n", Find(getrt(), read()));

	}

	return 0;

}