#include <fstream>
#include <cstdlib>
#include <ctime>
#define Refresh(C) C->size=(C->left)->size+(C->right)->size+1
#define Inf 100000000
using namespace std;
struct treap
{
int size,key,priority;
bool reversed;
treap *left, *right;
};
char Tip;
treap *Nod,*Nil,*Help1,*Help2,*Help3;
int i,j,N,Nr;
ifstream f("secv8.in");
ofstream g("secv8.out");
inline void Reverse(treap *C, int X)
{
treap *Aux;
if(C==Nil) return;
if(C->reversed)
{
C->reversed=0;
Aux=C->left;
C->left=C->right;
C->right=Aux;
if(C->left!=Nil) C->left->reversed^=1;
if(C->right!=Nil) C->right->reversed^=1;
}
if (X)
{
Reverse(C->left,0);
Reverse(C->right,0);
}
}
inline treap *Rotate_left(treap *C)
{
treap *Aux=C->left;
C->left=(C->left)->right;
Refresh(C);
Aux->right=C;
Refresh(Aux);
return Aux;
}
inline treap *Rotate_right(treap *C)
{
treap *Aux=C->right;
C->right=(C->right)->left;
Refresh(C);
Aux->left=C;
Refresh(Aux);
return Aux;
}
inline treap *Balance(treap *C)
{
if((C->left)->priority>C->priority)
return Rotate_left(C);
if((C->right)->priority>C->priority)
return Rotate_right(C);
return C;
}
inline treap *Insert(treap *C,int Local_key,int P,int Local_Priority)
{
if(C==Nil)
{
treap *Aux;
Aux=new treap;
Aux->left=Aux->right=Nil;
Aux->key=Local_key;
Aux->priority=Local_Priority;
Aux->size=1;
Aux->reversed=0;
return Aux;
}
Reverse(C,1);
if(P<=C->left->size+1) C->left=Insert(C->left,Local_key,P,Local_Priority);
else C->right=Insert(C->right,Local_key,P-C->left->size-1,Local_Priority);
C=Balance(C);
Refresh(C);
return C;
}
inline int Query(int Nr, treap *C)
{
Reverse(C,1);
if(C->left->size==Nr-1)
return C->key;
if(C->left->size<Nr)
return Query(Nr-(C->left->size)-1,C->right);
return Query(Nr,C->left);
}
inline treap *Delete(treap *C)
{
Reverse(C,1);
if(C->left==Nil&&C->right==Nil)
{
delete C;
return Nil;
}
if(C->left->priority > C->right->priority)
{
C=Rotate_left(C);
C->right=Delete(C->right);
}
else
{
C=Rotate_right(C);
C->left=Delete(C->left);
}
Refresh(C);
return C;
}
inline treap *Join(treap *A, treap *B)
{
treap *Aux;
Aux=new treap;
*Aux=*Nil;
Aux->left=A;
Aux->right=B;
return Delete(Aux);
}
inline void Split(int i,int j)
{
Help1=Help2=Help3=Nil;
Nod=Insert(Nod,0,i,Inf);
Help1=Nod->left;
Nod=Nod->right;
Nod=Insert(Nod,0,j-i+2,Inf);
Help2=Nod->left;
Help3=Nod->right;
}
inline void Write(treap *C)
{
if(C==Nil) return;
Reverse(C,1);
Write(C->left);
g<<C->key<<" ";
Write(C->right);
}
int main()
{
srand(time(0));
f>>N>>Tip;
Nil=new treap;
Nil->left=NULL;
Nil->right=NULL;
Nil->size=Nil->priority=Nil->reversed=0;
Nod=Nil;
while (N--)
{
f>>Tip;
if (Tip=='I')
{
f>>i>>Nr;
Nod=Insert(Nod,Nr,i,2);
}
if (Tip=='R')
{
f>>i>>j;
Split(i,j);
Help2->reversed^=1;
Nod=Join(Help1,Help2);
Nod=Join(Nod,Help3);
}
if (Tip=='A')
{
f>>i;
g<<Query(i,Nod)<<'\n';
}
if (Tip=='D')
{
f>>i>>j;
Split(i,j);
Nod=Join(Help1,Help3);
}
}
Write(Nod);
f.close();
g.close();
return 0;
}