#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
ifstream fin("secv8.in");
ofstream fout("secv8.out");
#define INF (1<<30)
#define cout fout
int a, b;
struct T{
int key, priority, s, r;
T *left, *right;
void rev()
{
if(priority && r)
{
r = 0;
left->r ^= 1;
right->r ^= 1;
swap(left, right);
}
}
void up()
{
if(priority == 0)
{
s = 0;
return;
}
s = 1;
if(left)
s+=left->s;
if(right)
s+=right->s;
}
T(int k, int p, T* l, T* re)
{
key = k;
priority = p;
left = l;
right = re;
s = 0;
r = 0;
}
} *R, *nil;
T *aux;
void af(T* &n)
{
if(n == nil)
return;
n->rev();
af(n->left);
cout << n->key << " ";
af(n->right);
}
void init()
{
srand(0);
R = nil = new T(0, 0, 0, 0);
}
void rotL(T* &n)
{
T* x = n->left;
n->rev();
x->rev();
n->left = x->right;
x->right = n;
x->up();
n->up();
n = x;
}
void rotR(T* &n)
{
T* x = n->right;
n->rev();
x->rev();
n->right = x->left;
x->left = n;
n->up();
x->up();
n = x;
}
void balance(T* &n)
{
n->rev();
if(n->left->priority > n->priority)
rotL(n);
else if(n->right->priority > n->priority)
rotR(n);
}
void insert(T* &n, int key, int priority, float value)
{
if(n == nil)
{
n = new T(key, priority, nil, nil);
n->up();
return;
}
n->up();
n->rev();
if(n->left->s + 1 > value)
{
insert(n->left, key, priority, value);
n->up();
}
else
{
insert(n->right, key, priority, value - (n->left->s + 1));
n->up();
}
balance(n);
}
int acces(T* &n, int k)
{
n->rev();
if(n->left->s >= k)
return acces(n->left, k);
if(n->left->s + 1 == k)
return n->key;
return acces(n->right, k-(n->left->s+1));
}
void erase_top(T* &n)
{
if(n == nil)
return;
n->rev();
n->left->rev();
n->right->rev();
if(n->left == nil && n->right == nil)
{
delete n;
n = nil;
return;
}
if(n->left->priority > n->right->priority)
{
rotL(n);
erase_top(n->right);
n->up();
}
else
{
rotR(n);
erase_top(n->left);
n->up();
}
}
void split(T* &n, T* &t1, T* &t2, float key)
{
n->rev();
insert(n, 0, INF, key);
n->up();
t1 = n->left;
t2 = n->right;
}
void join(T* &n, T* &t1, T* &t2)
{
n = new T(0, INF, t1, t2);
n->up();
erase_top(n);
}
void reverse(int i, int j)
{
T *t1, *t2, *t3, *t4;
split(R, t2, t4, j + 0.5);
t2->up();
t4->up();
split(t2, t1, t3, i - 0.5);
t1->up();
t3->up();
t4->up();
t1->rev();
t3->rev();
t4->rev();
t3->r ^= 1;
t3->rev();
aux = t2;
join(t2, t3, t4);
join(R, t1, t2);
}
void dele(T* &n)
{
if(n == nil)
return;
dele(n->left);
dele(n->right);
delete n;
n = nil;
}
void del(int i, int j)
{
T *t1, *t2, *t3, *t4;
split(R, t2, t4, j+0.5);
split(t2, t1, t3, i-0.5);
join(R, t1, t4);
dele(t3);
}
int main()
{
int n, x, k, i;
char c;
init();
fin>>n>>x;
for(i = 1; i<=n;i++)
{
fin>>c;
if(c == 'I')
{
fin>>a>>b;
insert(R, b, rand()+1, a - 0.5);
}
if(c == 'A')
{
fin>>k;
cout << acces(R, k) << "\n";
}
if(c == 'R')
{
fin>>a>>b;
reverse(a, b);
}
if(c == 'D')
{
fin>>a>>b;
del(a, b);
}
}
af(R);
}