#include<fstream>
#include<algorithm>
#include<vector>
#include<ctime>
#include<ctime>
#include<string>
using namespace std;
const char iname[]="secv8.in";
const char oname[]="secv8.out";
ifstream f(iname);
ofstream g(oname);
class treap
{
private:
class node
{
public:
int key,priority,reverse,sons;
node *left,*right;
node(int _key,int _priority,node* _left,node* _right):key(_key),priority(_priority),reverse(0),sons((_left ? _left->sons : 0)+(_right ? _right->sons : 0)+1),left(_left),right(_right){}
}*R;
void _get_sons(node* &r){r->sons=((r->left ? r->left->sons : 0)+(r->right ? r->right->sons : 0)+1);}
void _rot_left(node* &r)
{
node *aux=r->left;
r->left=aux->right;
aux->right=r;
_get_sons(r);_get_sons(aux);r=aux;
}
void _rot_right(node* &r)
{
node* aux=r->right;
r->right=aux->left;
aux->left=r;
_get_sons(r);_get_sons(aux);r=aux;
}
void _balance(node* &r)
{
if(r->left&&r->left->priority<r->priority)
_rot_left(r);
else
if(r->right&&r->right->priority<r->priority)
_rot_right(r);
else
_get_sons(r);
}
void _reverse(node* &r)
{
if(r==0)
return;
if(r->left)
r->left->reverse^=r->reverse;
if(r->right)
r->right->reverse^=r->reverse;
if(r->reverse)
{
node *aux=r->left;
r->left=r->right;
r->right=aux;
r->reverse=0;
}
}
void _insert(node* &r,int k,int key,int priority)
{
if(r==0)
{
r=new node(key,priority,NULL,NULL);
return;
}
_reverse(r);_reverse(r->left);_reverse(r->right);
if(k<=(r->left?r->left->sons:0))
_insert(r->left,k,key,priority);
else
_insert(r->right,(k-1-(r->left?r->left->sons:0)),key,priority);
_balance(r);
}
void _erase(node* &r)
{
if(r->left==0&&r->right==0)
{
delete r,r=0;
return;
}
_reverse(r),_reverse(r->left),_reverse(r->right);
if(r->left&&r->right)
if(r->left->priority<r->right->priority)
_rot_left(r),_erase(r->right);
else
_rot_right(r),_erase(r->left);
else
if(r->left)
_rot_left(r),_erase(r->right);
else
_rot_right(r),_erase(r->left);
_get_sons(r);
}
node* _find(node *r,int k)
{
_reverse(r);
if((r->left?r->left->sons:0)+1==k)
return r;
if(k<=(r->left?r->left->sons:0))
return _find(r->left,k);
else
return _find(r->right,k-(1+(r->left?r->left->sons:0)));
}
public:
void LRR(node *r)
{
if(r==0)
return;
_reverse(r);
LRR(r->left);
g<<r->key<<" ";
LRR(r->right);
}
void LRR()
{
LRR(R);
g<<"\n";
}
void insert(int x,int k)
{
_insert(R,k-1,x,rand()+1);
}
int find(int x)
{
return (_find(R,x))->key;
}
void erase(int x,int y)
{
node *Ts,*T,*Tg;
_insert(R,x-1,0,0);
Ts=R->left;
_insert(R->right,y-x+1,0,0);
T=R->right->left;
Tg=R->right->right;
delete R->right;
delete R;
R=new node(0,0,Ts,Tg);
_erase(R);
}
void reverse(int x,int y)
{
node *Ts,*T,*Tg;
_insert(R,x-1,0,0);
Ts=R->left;
_insert(R->right,y-x+1,0,0);
T=R->right->left;
Tg=R->right->right;
T->reverse^=1;
_reverse(T);
delete R->right,delete R;
R=new node(0,0,Ts,T);
_erase(R);
T=R,R=new node(0,0,T,Tg);
_erase(R);
}
treap():R(0)
{
srand(time(NULL));
}
} T;
string aux;
int n,x,i,y;
int main()
{
f>>n>>x;
f.get();
for(i=1;i<=n;++i)
{
f>>aux;
if(aux=="I")
f>>x>>y,T.insert(y,x);
else
if(aux=="A")
{
f>>x;
y=T.find(x);
g<<y<<"\n";
}
else
if(aux=="R")
f>>x>>y,T.reverse(x,y);
else
f>>x>>y,T.erase(x,y);
f.get();
}
T.LRR();
f.close();
g.close();
return 0;
}