#include <bits/stdc++.h>
using namespace std ;
ifstream fin("secv8.in") ;
ofstream fout("secv8.out") ;
struct treap
{
int key , priority , sz;
treap *left ;
treap *right ;
treap () {}
treap ( int key , int priority , int sz , treap *left , treap *right )
{
this->key=key;
this->priority=priority ;
this->sz=sz;
this->left=left;
this->right=right;
}
};
treap *nill , *root;
void sizenou(treap * &nod)
{
if ( nod == nill )
return ;
nod->sz = nod->left->sz+nod->right->sz+1 ;
}
void rotleft(treap * &nod)
{
treap *t = nod->left;
nod->left = t->right ;
t->right = nod ;
nod = t;
sizenou(nod->right) ;
sizenou(nod);
}
void rotright(treap * &nod )
{
treap *t = nod->right ;
nod->right = t->left ;
t->left = nod ;
nod = t ;
sizenou(nod->left) ;
sizenou(nod);
}
void balance(treap * &nod)
{
if ( nod->left->priority > nod->priority )
rotleft(nod) ;
else if ( nod->right->priority > nod->priority )
rotright(nod) ;
}
void adaug(treap * &nod , int key , int poz,int priority)
{
if ( nod == nill )
{
nod = new treap(key,priority,1,nill,nill) ;
return ;
}
if ( nod->left->sz+1 >= poz )
adaug(nod->left,key,poz,priority) ;
else
adaug(nod->right,key,poz-nod->left->sz-1,priority) ;
sizenou(nod) ;
balance(nod) ;
}
int cauta(treap *nod,int poz)
{
if ( nod == nill || nod->left->sz+1 == poz )
return nod->key;
if ( nod->left->sz+1 > poz )
return cauta(nod->left,poz) ;
else
return cauta(nod->right,poz-nod->left->sz-1) ;
}
void inordine(treap *nod )
{
if ( nod == nill )
return ;
inordine(nod->left) ;
fout << nod->key << " " ;
inordine(nod->right) ;
}
void sterg(treap * &nod)
{
if ( nod == nill )
return ;
if ( nod->left==nill&&nod->right==nill )
{
delete nod ;
nod = nill ;
return ;
}
if ( nod->left->priority >= nod->right->priority )
rotleft(nod) ;
else
rotright(nod) ;
if ( nod->left->priority == -1 )
sterg(nod->left) ;
else
sterg(nod->right) ;
sizenou(nod) ;
}
void split(treap* &a , treap* &b , int poz )
{
adaug(a,0,poz,0x3f3f3f3f) ;
treap *aux = a ;
a = aux->left;
b = aux->right;
delete aux;
}
treap * join (treap * &t1 , treap * &t2 )
{
treap * nod = new treap(0,-1,t1->sz+1+t2->sz,t1,t2) ;
sterg(nod) ;
return nod;
}
void Delete(treap * &nod , int left , int right )
{
treap * a = nod , *b , *c;
split(a,b,left) ;
split(b,c,right-left+2) ;
nod = join(a,c) ;
}
int main()
{
srand(time(NULL));
int i , rv , n , k , e;
char ch;
root=nill=new treap(0,0,0,NULL,NULL) ;
fin >> n >> rv;
for ( i = 1 ; i <= n ; i++ )
{
fin >> ch ;
if ( ch == 'I' )
{
fin >> k >> e;
adaug(root,e,k,rand()+1) ;
}
else if ( ch == 'A' )
{
fin >> k ;
fout << cauta(root,k) << '\n' ;
}
else if ( ch == 'D' )
{
fin >> k >> e ;
Delete(root,k,e) ;
}
/*else if ( ch == 'R' )
{
}*/
}
inordine(root) ;
fout << '\n' ;
return 0;
}