#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

inline int read(){
	register int x = 0, f = 1; register char ch;
	for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1;
	for(; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0'); 
	return x * f;
}

const int N = 8e4 + 10;

int t[N][2];//左右儿子 
int n, tot;
int val[N], fa[N];
int cnt[N], size[N];
int rt;
int pos[N];

void updata(int x){
	size[x] = size[t[x][0]] + size[t[x][1]] + 1;// 左加右加自身 
//	pos[val[t[x][0]]] = t[x][0]; pos[val[t[x][1]]] = t[x][1];
} 

void rot(int x){
	int y = fa[x], z = fa[y], k = (t[y][1] == x), w = t[x][k ^ 1]; // k为x在y的儿子位置，w为x的另一位置的儿子 
	if(z) t[z][t[z][1] == y] = x; fa[x] = z; //如果有爷爷，爸爸所在的位置被x替代，x的父亲变成z
	fa[fa[t[t[x][k ^ 1] = y][k] = w] = y] = x; //  1.x为y左儿子说明y应该在x左边右儿子反之，所以k^1，此时替代了w；2.x是y的左儿子说明x包括子树点权都小于y应该是y的左儿子，反之易得，所以k；3.fa[w] = y;4.fa[y] = x;
	updata(y); updata(x); // 先把y（x子树）upd再updx； 
}

void SPY(int x, int ps){// 把x转到pos的直接儿子 
	while(fa[x] != ps){
		int y = fa[x], z = fa[y]; // 爸爸，爷爷
		if(z != ps) rot((t[z][1] == y) ^ (t[y][1] == x) ? x : y); // 在z不是pos的时候（如果是会转走）看看xyz是否是直线（相同为0不同为1）是的话转y不是的话转x
		rot(x); //x一定转一次 
	}
//	pos[val[x]] = x;
	if(!ps) rt = x; //父亲为0即根； 
}

void insert(int w){ // 插入w
	int x = rt, y = 0; // x为当前找到的点， y为他的父亲
	while(t[rt][1]) x = t[rt][1];
	fa[++ tot] = x; t[x][1] = tot; val[tot] = w; pos[w] = tot, size[tot] = 1;
	SPY(tot, 0);
}

inline void ist_top(int w){
	SPY(pos[w], 0);
	if(!t[rt][0]) return;
	if(!t[rt][1]) t[rt][1] = t[rt][0], t[rt][0] = 0;
	else{
		int x = t[rt][1]; while(t[x][0]) x = t[x][0];
		fa[t[rt][0]] = x; t[x][0] = t[rt][0]; t[rt][0] = 0;
		SPY(t[x][0], 0);
	}
}

inline void ist_bottom(int w){
	SPY(pos[w], 0);
	if(!t[rt][1]) return;
	if(!t[rt][0]) t[rt][0] = t[rt][1], t[rt][1] = 0;
	else{
		int x = t[rt][0]; while(t[x][1]) x = t[x][1];
		fa[t[rt][1]] = x; t[x][1] = t[rt][1]; t[rt][1] = 0;
		SPY(t[x][1], 0);
	}
}

void in_pos(int w, int tt){
	SPY(pos[w], 0);
	if(!tt) return;
	if(tt == 1){
		int x = t[rt][1]; while(t[x][0]) x = t[x][0];
		int ps = pos[w];
		swap(pos[w], pos[val[x]]);
		swap(val[ps], val[x]);
	}
	else{
		int x = t[rt][0];
		while(t[x][1]) 
		x = t[x][1];
		int ps = pos[w];
		swap(pos[w], pos[val[x]]);
		swap(val[ps], val[x]);
	}
}

int query(int w){
	int x = rt; 
	while(1){
		if(size[t[x][0]] + 1 == w) return val[x];
		else if(size[t[x][0]] >= w) x = t[x][0];
		else w -= size[t[x][0]] + 1, x = t[x][1];
	}
}

int m;
char st[10];

int main(){
	n = read(); m = read();
	for(int i = 1; i <= n; ++ i){
		int a = read();
		insert(a);
	}
	
	for(int i = 1; i <= m; ++ i){
		std :: cin >> st;
		if(st[0] == 'T'){
			int a = read();
			ist_top(a);
		}
		else if(st[0] == 'B'){
			int a = read();
			ist_bottom(a);
		}
		else if(st[0] == 'I'){
			int a = read(), b = read();
			in_pos(a, b);
		}
		else if(st[0] == 'A'){
			int a = read();
			SPY(pos[a], 0);
			printf("%d\n", size[t[pos[a]][0]]);
			
		}
		else if(st[0] == 'Q'){
			int a = read();
			printf("%d\n", query(a));
		}
	}
}
/*
10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2
*/

1.这份代码里pos的真正意义是什么

2.是根据什么建的平衡树