#include <fstream>
#include <cstdlib>
#include <ctime>
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 Reverse(Treap*& Node, int Depth)
{
if(Node == Nil || Depth == 0)
return;
if(Node -> left != Nil)
Node -> left -> rev ^= Node -> rev;
if(Node -> right != Nil)
Node -> right -> rev ^= Node -> rev;
if(Node -> rev == 1)
swap(Node -> left, Node -> right), Node -> rev = 0;
Reverse(Node -> left, Depth - 1);
Reverse(Node -> right, Depth - 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;
}
Reverse(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 Erase(Treap*& Node)
{
if(Node == Nil)
return;
Reverse(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*& Root, Treap*& NewRoot, int Pos)
{
Insert(Root, Pos, 0, 2147483647);
Treap* Aux = Root;
Root = Aux -> left;
NewRoot = Aux -> right;
delete Aux;
}
Treap * Join(Treap*& T1, Treap*& T2)
{
Treap* newRoot = new Treap(T1 -> sz + T2 -> sz + 1, 0, -1, T1, T2);
Erase(newRoot);
return newRoot;
}
void Erase(Treap *& Root, int Left, int Right)
{
Treap * A = Root, *B, *C;
Split(A, B, Left);
Split(B, C, Right + 1 - Left + 1);
Root = Join(A, C);
}
void Rev(Treap *& Root, int Left, int Right)
{
Treap * A = Root, *B, *C;
Split(A, B, Left);
Split(B, C, Right + 1 - Left + 1);
B -> rev ^= 1;
Root = Join(A, B);
Root = Join(R, C);
}
int Acces(Treap *& Node, int Pos)
{
Reverse(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;
Reverse(Node, 2);
Inorder(Node -> left);
g << Node -> key << " ";
Inorder(Node -> right);
}
int main()
{
f >> N >> type;
R = Nil = new Treap(0, 0, 0, NULL, NULL);
srand(time(NULL));
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;
Erase(R, k, e);
}
if(t == 'A')
{
int k;
f >> k;
g << Acces(R, k) << "\n";
}
}
Inorder(R);
g << "\n";
return 0;
}