#include <bits/stdc++.h>
using namespace std;
ifstream f("secv8.in");
ofstream g("secv8.out");
int N, type;
struct Treap{
int key, priority, sz, rev;
Treap * left;
Treap * right;
Treap(int size, int key, int priority, Treap * left, Treap * right)
{
this -> key = key;
this -> priority = priority;
this -> left = left;
this -> right = right;
this -> rev = 0;
this -> sz = size;
}
};
Treap * R, * Nil;
void Update(Treap*& Node)
{
if(Node == Nil)
return;
Node -> sz = Node -> left -> sz + Node -> right -> sz + 1;
}
void revers(Treap * &nod , int df )
{
if ( nod == Nil || df == 0 )
return ;
if ( nod->left != Nil )
nod->left->rev = nod->left->rev^nod->rev;
if ( nod->right != Nil )
nod->right->rev = nod->right->rev ^ nod->rev;
if ( nod->rev == 1 )
{
swap(nod->left,nod->right) ;
nod->rev = 0;
}
revers(nod->left,df-1) ;
revers(nod->right,df-1) ;
}
void RotLeft(Treap*& Node)
{
Treap* T = Node -> left;
Node -> left = T -> right;
T -> right = Node;
Node = T;
Update(Node -> right);
Update(Node);
}
void RotRight(Treap*& Node)
{
Treap* T = Node -> right;
Node -> right = T -> left;
T -> left = Node;
Node = T;
Update(Node -> left);
Update(Node);
}
void Balance(Treap*& Node)
{
if(Node -> left -> priority > Node -> priority)
RotLeft(Node);
else
if(Node -> right -> priority > Node -> priority)
RotRight(Node);
}
void Insert(Treap*& Node, int Pos, int Key, int Priority)
{
if(Node == Nil)
{
Node = new Treap(1, Key, Priority, Nil, Nil);
return;
}
revers(Node, 2);
if(Node -> left -> sz + 1 >= Pos)
Insert(Node -> left, Pos, Key, Priority);
else
Insert(Node -> right, Pos - Node -> left -> sz - 1, Key, Priority);
Update(Node);Balance(Node);
}
void sterg(Treap * &nod)
{
if ( nod == Nil )
return ;
revers(nod,2) ;
if ( nod->left == Nil && nod->right == Nil )
{
delete nod ;
nod = Nil ;
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) ;
Update(nod) ;
}
void Erase(Treap*& Node)
{
if(Node == Nil)
return;
revers(Node, 2);
if(Node -> left == Nil && Node -> right == Nil)
{
delete Node, Node = Nil;
return;
}
if(Node -> left -> priority >= Node -> right -> priority)
{
RotLeft(Node);
}
else
RotRight(Node);
if(Node -> left -> priority == -1)
{
Erase(Node -> left);
}
else
Erase(Node -> right);
Update(Node);
}
void split(Treap* &a , Treap* &b , int poz )
{
Insert(a,poz,0,0x3f3f3f3f) ;
Treap *aux = a ;
a = aux->left;
b = aux->right;
delete aux;
}
Treap * join (Treap * &t1 , Treap * &t2 )
{
Treap * nod = new Treap(t1->sz + 1 + t2->sz ,0,-1,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) ;
}
void rev(Treap* &nod , int left , int right )
{
Treap * a = nod , *b , *c ;
split(a,b,left) ;
split(b,c,right-left+2) ;
b->rev = b->rev^1 ;
nod = join(a,b) ;
nod = join(R,c) ;
}
int Acces(Treap *& Node, int Pos)
{
revers(Node, 1);
if(Node == Nil || Node -> left -> sz + 1 == Pos)
return Node -> key;
if(Node -> left -> sz + 1 < Pos)
return Acces(Node -> right, Pos - Node -> left -> sz - 1);
else
return Acces(Node -> left, Pos);
}
void Inorder(Treap*& Node)
{
if(Node == Nil)
return;
revers(Node, 2);
Inorder(Node -> left);
g << Node -> key << " ";
Inorder(Node -> right);
}
int main()
{
srand(time(NULL));
int i , rv , n , k , e;
char ch;
R = Nil = new Treap(0,0,0,NULL,NULL) ;
f >> N >> type;
for(int i = 1; i <= N; i++)
{
char t;
f >> t;
if(t == 'I')
{
int k, e;
f >> k >> e;
Insert(R, k, e, rand() + 1);
}
if(t == 'R')
{
int k, e;
f >> k >> e;
rev(R, k, e);
}
if(t == 'D')
{
int k, e;
f >> k >> e;
Delete(R, k, e);
}
if(t == 'A')
{
int k;
f >> k;
g << Acces(R, k) << "\n";
}
}
Inorder(R);
g << "\n";
return 0;
}