#include <bits/stdc++.h>
#define MaxN 100005
#define INF 2140000000
#define MOD 1000000007
using namespace std;
FILE*IN,*OUT;
int N,X,Y;
char C;
struct Treap
{
int priority,value,weight;
bool reversed;
Treap *left,*right;
Treap(int val=0,Treap *NILL=NULL)
{
reversed=0;
priority=rand();
value=val;
weight=1;
left=right=NILL;
}
}*NIL;
void Do_Reverse(Treap *T)
{
if(T->reversed)
{
T->reversed=0;
swap(T->left,T->right);
if(T->left!=NIL)
T->left->reversed^=1;
if(T->right!=NIL)
T->right->reversed^=1;
}
}
void recalculate(Treap *T)
{
T->weight=1+T->left->weight+T->right->weight;
}
Treap *join(Treap *Treap1,Treap *Treap2)
{
if(Treap1==NIL)
return Treap2;
if(Treap2==NIL)
return Treap1;
Do_Reverse(Treap1);
Do_Reverse(Treap2);
if(Treap1->priority>=Treap2->priority)
{
Treap1->left=join(Treap1->left,Treap2);
recalculate(Treap1);
return Treap1;
}
else
{
Treap2->right=join(Treap1,Treap2->right);
recalculate(Treap2);
return Treap2;
}
}
pair<Treap*,Treap*> split(Treap *T,int Size)
{
if(T==NIL)
return make_pair(NIL,NIL);
Do_Reverse(T);
if(Size<=T->right->weight)
{
pair<Treap*,Treap*>Temp;
Temp=split(T->right,Size);
T->right=Temp.second;
recalculate(T);
return make_pair(Temp.first,T);
}
else if(Size==1+T->right->weight)
{
pair<Treap*,Treap*>Temp;
Temp=make_pair(T->right,T);
T->right=NIL;
recalculate(T);
return Temp;
}
else
{
pair<Treap*,Treap*>Temp;
Temp=split(T->left,Size-1-T->right->weight);
T->left=Temp.first;
recalculate(T);
return make_pair(T,Temp.second);
}
}
void Insert(Treap*&T,int val,int key)
{
Treap* Added=new Treap(val,NIL);
pair<Treap*,Treap*>Temp=split(T,key);
T=join(Temp.first,join(Added,Temp.second));
}
void Delete(Treap *&T,int key1,int key2)
{
pair<Treap*,Treap*>Temp=split(T,key1);
pair<Treap*,Treap*>Temp2=split(Temp.second,key2-key1+2);
T=join(Temp.first,Temp2.second);
}
int GetVal(Treap*T,int pos)
{
Do_Reverse(T);
if(T->right->weight>=pos)
return GetVal(T->right,pos);
else if(T->right->weight+1==pos)
return T->value;
else return GetVal(T->left,pos-1-T->right->weight);
}
void Reverse(Treap *&T,int key1,int key2)
{
pair<Treap*,Treap*>Temp=split(T,key1);
pair<Treap*,Treap*>Temp2=split(Temp.second,key2-key1+2);
Temp2.first->reversed^=1;
T=join(Temp.first,join(Temp2.first,Temp2.second));
}
void WalkThrough(Treap*T)
{
Do_Reverse(T);
if(T->right!=NIL)
WalkThrough(T->right);
fprintf(OUT,"%d ",T->value);
if(T->left!=NIL)
WalkThrough(T->left);
}
int main()
{
IN=fopen("secv8.in","r");
OUT=fopen("secv8.out","w");
srand(time(NULL));
NIL=new Treap();
NIL->weight=0;
Treap*Root=NIL;
fscanf(IN,"%d %d ",&N,&X);
for(int i=1;i<=N;i++)
{
fscanf(IN,"%c",&C);
if(C=='I')
{
fscanf(IN,"%d%d ",&X,&Y);
Insert(Root,Y,X);
}
else if(C=='A')
{
fscanf(IN,"%d ",&X);
fprintf(OUT,"%d\n",GetVal(Root,X));
}
else if(C=='R')
{
fscanf(IN,"%d%d ",&X,&Y);
Reverse(Root,X,Y);
}
else if(C=='D')
{
fscanf(IN,"%d%d ",&X,&Y);
Delete(Root,X,Y);
}
}
WalkThrough(Root);
return 0;
}