#include<bits/stdc++.h>
using namespace std;
struct Node{
	int l,r,key,val,val2,len;
}a[200001],b[200001];
const int md=1000000;
int tot=0,rot,rotb,totb;
void push_up(int p){
	a[p].len=a[a[p].l].len+a[a[p].r].len+1;
}
void Push_up(int p){
	b[p].len=b[b[p].l].len+b[b[p].r].len+1;
}
//-----------------------------------------合并 
int merge(int rot1,int rot2){
	if(rot1==0){
		return rot2;
	}
	else if(rot2==0){
		return rot1;
	}
	if(a[rot1].key<a[rot2].key){
		a[rot1].r=merge(a[rot1].r,rot2);
		push_up(rot1);
		return rot1;
	}
	else{
		a[rot2].l=merge(rot1,a[rot2].l);
		push_up(rot2);
		return rot2;
	}
}
int Merge(int rot1,int rot2){
	if(rot1==0){
		return rot2;
	}
	else if(rot2==0){
		return rot1;
	}
	if(b[rot1].key<b[rot2].key){
		b[rot1].r=Merge(b[rot1].r,rot2);
		Push_up(rot1);
		return rot1;
	}
	else{
		b[rot2].l=Merge(rot1,b[rot2].l);
		Push_up(rot2);
		return rot2;
	}
}
//-----------------------------------------按权值拆 
void val_split(int now,int k,int &rot1,int &rot2){
	if(now==0){
		rot1=0;
		rot2=0;
		return;
	}
	else if(a[now].val<=k){
		rot1=now;
		val_split(a[rot1].r,k,a[rot1].r,rot2);
	}
	else{
		rot2=now;
		val_split(a[rot2].l,k,rot1,a[rot2].l);
	}
	push_up(now);
}
void Val_split(int now,int k,int &rot1,int &rot2){
	if(now==0){
		rot1=0;
		rot2=0;
		return;
	}
	else if(b[now].val<=k){
		rot1=now;
		Val_split(b[rot1].r,k,b[rot1].r,rot2);
	}
	else{
		rot2=now;
		Val_split(b[rot2].l,k,rot1,b[rot2].l);
	}
	Push_up(now);
}
//-----------------------------------------按排名拆 
void k_split(int now,int k,int &rot1,int &rot2){
	if(now==0){
		rot1=0;
		rot2=0;
		return;
	}
	push_up(now);
	if(a[a[now].l].len<k){
		rot1=now;
		k_split(a[rot1].r,k-a[a[rot1].l].len-1,a[rot1].r,rot2);
	}
	else{
		rot2=now;
		k_split(a[rot2].l,k,rot1,a[rot2].l);
	}
	push_up(now);	
}
void K_split(int now,int k,int &rot1,int &rot2){
	if(now==0){
		rot1=0;
		rot2=0;
		return;
	}
	Push_up(now);
	if(b[b[now].l].len<k){
		rot1=now;
		K_split(b[rot1].r,k-b[b[rot1].l].len-1,b[rot1].r,rot2);
	}
	else{
		rot2=now;
		K_split(b[rot2].l,k,rot1,b[rot2].l);
	}
	Push_up(now);	
}
//-------------------------------------新建节点 
void New_Node(int val,int i){
	a[++tot].key=rand()%11451450+1;
	a[tot].l=0;
	a[tot].r=0;
	int rot1,rot2,now=tot;
	a[tot].len=1;
	a[tot].val=val;
	a[tot].val2=i;
	val_split(rot,val,rot1,rot2);
	rot=merge(merge(rot1,now),rot2);
}
void new_Node(int i,int val){
	b[++totb].key=rand()%11451450+1;
	b[totb].l=0;
	b[totb].r=0;
	int rot1,rot2,now=totb;
	b[totb].len=1;
	b[totb].val=val;
	b[totb].val2=i;
	Val_split(rotb,val,rot1,rot2);
	rotb=Merge(Merge(rot1,now),rot2);
}
//-------------------------------------删除 
void Erase(int val){
	int rot1,rot2,rot3,rot4;
	val_split(rot,val-1,rot1,rot2);
	k_split(rot2,1,rot3,rot4);
	rot=merge(rot1,rot4);
}
void erase(int val){
	int rot1,rot2,rot3,rot4;
	Val_split(rotb,val-1,rot1,rot2);
	K_split(rot2,1,rot3,rot4);
	rotb=Merge(rot1,rot4);
}
//-------------------------------------查找 
int Find_k(int val){
	int rot1,rot2;
	val_split(rot,val-1,rot1,rot2);	
	int x=a[rot1].len;
	rot=merge(rot1,rot2);
	return x;
}
int find_k(int val){
	int rot1,rot2;
	Val_split(rotb,val-1,rot1,rot2);	
	int x=b[rot1].len;
	rotb=Merge(rot1,rot2);
	return x;
}
int Find_val(int k){
	int rot1,rot2,rot3,rot4;
	k_split(rot,k-1,rot1,rot2);
	k_split(rot2,1,rot3,rot4);
	int x=a[rot3].val;
	rot=merge(rot1,merge(rot3,rot4));
	return x;
}
int find_val(int k){
	int rot1,rot2,rot3,rot4;
	K_split(rotb,k-1,rot1,rot2);
	K_split(rot2,1,rot3,rot4);
	int x=b[rot3].val;
	rotb=Merge(rot1,Merge(rot3,rot4));
	return x;
}
int Find_last(int val){
	int rot1,rot2,rot3,rot4;
	val_split(rot,val,rot1,rot2);
	k_split(rot1,a[rot1].len-1,rot3,rot4);
	int x=a[rot4].val;
	rot=merge(merge(rot3,rot4),rot2);
	return x;
}
int find_last(int val){
	int rot1,rot2,rot3,rot4;
	Val_split(rotb,val-1,rot1,rot2);
	K_split(rot1,b[rot1].len-1,rot3,rot4);
	int x=b[rot4].val;
	rotb=Merge(Merge(rot3,rot4),rot2);
	return x;
}
int Find_next(int val){
	int rot1,rot2,rot3,rot4;
	val_split(rot,val-1,rot1,rot2);
	k_split(rot2,1,rot3,rot4);
	int x=a[rot3].val;
	rot=merge(rot1,merge(rot3,rot4));
	return x;
}
int find_next(int val){
	int rot1,rot2,rot3,rot4;
	Val_split(rotb,val,rot1,rot2);
	K_split(rot2,1,rot3,rot4);
	int x=b[rot3].val;
	rotb=Merge(rot1,Merge(rot3,rot4));
	return x;
}
int Find(int val){
	int rot1,rot2,rot3,rot4;
	val_split(rot,val-1,rot1,rot2);
	k_split(rot2,1,rot3,rot4);
	int x=rot3;
	rot=merge(rot1,merge(rot3,rot4));
	return rot3;
}
int find(int val){
	int rot1,rot2,rot3,rot4;
	Val_split(rotb,val-1,rot1,rot2);
	K_split(rot2,1,rot3,rot4);
	int x=rot3;
	rotb=Merge(rot1,Merge(rot3,rot4));
	return rot3;
}
//------------------------------------主函数 
int main(){
	srand(time(NULL));
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int val;
		scanf("%d",&val);
		New_Node(val,i); 
		new_Node(val,i);
	} 
	int l=1,r=n;
	for(int i=1;i<=m;i++){
		string s;
		cin>>s;
		if(s=="Top"){
			int x;
			scanf("%d",&x);
			int bj=Find(x);
			Erase(x);
			erase(a[bj].val2);
			new_Node(x,--l);
			New_Node(x,l);
		}
		else if(s=="Bottom"){
			int x;
			scanf("%d",&x);
			int bj=Find(x);
			Erase(x);
			erase(a[bj].val2);
			new_Node(x,++r);
			New_Node(x,r);
		}
		else if(s=="Insert"){
			int x,t;
			scanf("%d%d",&x,&t);
			if(t==0){
				continue;
			}
			int bj=Find(x);//a1
			int bj1=find_k(a[bj].val2);
			int bj2=find_val(bj1+t);
			int bj3=find(bj2);//b2
			//int bj4=find(a[bj].val2);//b1
			//int bj5=Find(b[bj3].val2);//a2
			Erase(a[bj].val);
			Erase(b[bj3].val2);
			erase(a[bj].val2);
			erase(b[bj3].val);
			//cout<<bj<<' '<<bj3<<'\n';
			New_Node(a[bj].val,b[bj3].val);
			New_Node(b[bj3].val2,a[bj].val2);
			new_Node(a[bj].val,b[bj3].val);
			new_Node(b[bj3].val2,a[bj].val2);
		}
		else if(s=="Ask"){
			int x;
			scanf("%d",&x);
			int bj=Find(x);
			int ans=find_k(a[bj].val2);
			printf("%d\n",ans);
		}
		else{
			int x;
			scanf("%d",&x);
			int bj=find_val(x);
			int bj2=find(bj);
			printf("%d\n",b[bj2].val2);
			//cout<<bj<<"  "<<bj2<<"  "<<b[3].val2<<'\n';
		}
	}
	//for(int i=1;i<=totb;i++){
	//	cout<<i<<' '<<b[i].val<<' '<<b[i].val2<<'\n';
	//}
	//cout<<"-------------------------------------------------------------------"<<'\n';
	//for(int i=1;i<=totb;i++){
	//	cout<<i<<' '<<a[i].val<<' '<<a[i].val2<<'\n';
	//}
	return 0;
}