#include<stdio.h>
#include<cstdlib>
#include<ctime>
FILE*f=fopen("secv8.in","r");
FILE*g=fopen("secv8.out","w");
const int INF = (1LL<<31)-1;
struct node{
int key,priority,subarb,reverse;
node *ls,*rs;
node ( int _key , int _priority , node *_ls , node *_rs , int real ){
key = _key; priority = _priority;
ls = _ls; rs = _rs;
subarb = real;
if ( _ls != NULL ) subarb += _ls->subarb;
if ( _rs != NULL ) subarb += _rs->subarb;
reverse = 0;
}
};
node *R,*nul,*aux;
inline void update ( node *&nod ){
if ( nod == nul ){
nod->subarb = 0;
return ;
}
if ( nod == NULL ) return ;
nod->subarb = 1;
if ( nod->ls != NULL ) nod->subarb += nod->ls->subarb;
if ( nod->rs != NULL ) nod->subarb += nod->rs->subarb;
}
inline void propaga ( node *&nod ){
if ( nod->reverse ){
aux = nod->ls; nod->ls = nod->rs; nod->rs = aux;
}
if ( nod->ls != nul )
nod->ls->reverse ^= nod->reverse;
if ( nod->rs != nul )
nod->rs->reverse ^= nod->reverse;
nod->reverse = 0;
}
inline void rotate_ls ( node *&nod ){
propaga(nod->ls);
node *fiu = nod->ls;
nod->ls = fiu->rs;
fiu->rs = nod;
update(nod); update(fiu);
nod = fiu;
}
inline void rotate_rs ( node *&nod ){
propaga(nod->rs);
node *fiu = nod->rs;
nod->rs = fiu->ls;
fiu->ls = nod;
update(nod); update(fiu);
nod = fiu;
}
inline void balance ( node *&nod ){
if ( nod->ls->priority > nod->priority && nod->ls->priority > nod->rs->priority ){
rotate_ls(nod);
}
else{
if ( nod->rs->priority > nod->priority ){
rotate_rs(nod);
}
}
update(nod);
}
void insert ( node *&nod , int k , int key , int priority ){
propaga(nod);
if ( nod->ls->subarb == k - 1 ){
nod->subarb -= nod->ls->subarb;
node *aux = new node(key,priority,nod->ls,nod,1);
nod->ls = nul;
nod = aux;
}
else{
if ( nod->ls->subarb >= k ){
insert(nod->ls,k,key,priority);
}
else{
insert(nod->rs,k-nod->ls->subarb-1,key,priority);
}
}
balance(nod);
}
void query ( node *&nod , int k , int &answer ){
propaga(nod);
if ( nod->ls->subarb == k - 1 ){
answer = nod->key;
return ;
}
else{
if ( nod->ls->subarb >= k ){
query(nod->ls,k,answer);
}
else{
query(nod->rs,k-nod->ls->subarb-1,answer);
}
}
}
inline void split ( node *&nod , int poz , node *&T1 , node *&T2 ){
insert(nod,poz,0,INF);
T1 = nod->ls; T2 = nod->rs;
delete nod; nod = nul;
}
void erase ( node *&nod ){
propaga(nod);
if ( nod->ls == nul && nod->rs == nul ){
delete nod; nod = nul;
}
else{
if ( nod->ls->priority > nod->rs->priority ){
rotate_ls(nod);
erase(nod->rs);
}
else{
rotate_rs(nod);
erase(nod->ls);
}
}
update(nod);
}
void afiseaza ( node *nod ){
propaga(nod);
if ( nod->ls != nul ){
afiseaza(nod->ls);
}
fprintf(g,"%d ",nod->key);
if ( nod->rs != nul ){
afiseaza(nod->rs);
}
}
inline void join ( node *&R , node *&T1 , node *&T2 ){
int priority = rand()+1;
R = new node(0,priority,T1,T2,1);
erase(R);
}
int main () {
int m,aux;
fscanf(f,"%d %d\n",&m,&aux);
srand(time(NULL));
R = nul = new node(0,0,NULL,NULL,0);
R->ls = nul; R->rs = nul;
char tip;
for ( int ii = 1 ; ii <= m ; ++ii ){
fscanf(f,"%c",&tip);
if ( tip == 'I' ){
int poz,val;
fscanf(f,"%d %d\n",&poz,&val);
int pr = rand()+1;
insert(R,poz,val,pr);
}
else{
if ( tip == 'A' ){
int poz;
fscanf(f,"%d\n",&poz);
int answer;
query(R,poz,answer);
fprintf(g,"%d\n",answer);
}
else{
if ( tip == 'D' ){
int i,j;
fscanf(f,"%d %d\n",&i,&j);
node *T1,*T2,*T3,*T4;
split(R,i,T1,T2);
split(T2,j-i+2,T3,T4);
join(R,T1,T4);
}
else{
if ( tip == 'R' ){
int i,j;
fscanf(f,"%d %d\n",&i,&j);
node *T1,*T2,*T3,*T4;
split(R,i,T1,T2);
split(T2,j-i+2,T3,T4);
T3->reverse = !T3->reverse;
join(T2,T1,T3);
join(R,T2,T4);
}
}
}
}
}
afiseaza(R);
fprintf(g,"\n");
fclose(f);
fclose(g);
return 0;
}