#include <iostream>
#include <fstream>
#include <vector>
#include <cstdlib>
using namespace std;
ifstream fin ("secv8.in");
ofstream fout ("secv8.out");
const int INF = 2e9;
class Treap {
public:
Treap () {
R = NILL = new Node (0, 0, 0, nullptr, nullptr);
}
void Print () {
m_Print (R);
fout << '\n';
}
void Insert (int value, int position) {
m_Insert (value, rand () + 1, position, R);
}
void Access (int position) {
m_Access (position, R);
}
void Reverse (int i, int j) {
m_Reverse (i, j);
}
void Remove (int i, int j) {
m_Remove (i, j);
}
private:
struct Node {
Node (int v, int h, int p, Node *l, Node *r) {
this -> value = v;
this -> howMany = h;
this -> priority = p;
this -> left = l;
this -> right = r;
this -> lazy = false;
}
bool lazy;
Node *left, *right;
int value, howMany, priority;
};
Node *R, *NILL;
void m_Debug (Node *curNode) {
cerr << "value: " << curNode -> value << '\n'
<< "howMany: " << curNode -> howMany << '\n'
<< "priority: " << curNode -> priority << '\n'
<< "lazy: " << curNode -> lazy << '\n'
<< "left -> value: " << curNode -> left -> value << '\n'
<< "right -> value: " << curNode -> right -> value << '\n'
<< "left -> howMany: " << curNode -> left -> howMany << '\n'
<< "right -> howMany: " << curNode -> right -> howMany << '\n'
<< "-----------------------------\n\n";
}
void m_Print (Node *&curNode) {
m_Propagate (curNode);
if (curNode == NILL) {
return;
}
m_Print (curNode -> left);
fout << curNode -> value << ' ';
m_Print (curNode -> right);
}
void m_UpdateHM (Node *&curNode) {
if (curNode == NILL) {
return;
}
curNode -> howMany = curNode -> left -> howMany + curNode -> right -> howMany + 1;
}
void m_Propagate (Node *&curNode) {
if (curNode == nullptr or curNode == NILL or curNode -> lazy == false) {
return;
}
Node *aux = curNode -> left;
curNode -> left = curNode -> right;
curNode -> right = aux;
curNode -> lazy = false;
if (curNode -> left != NILL) {
curNode -> left -> lazy ^= 1;
}
if (curNode -> right != NILL) {
curNode -> right -> lazy ^= 1;
}
}
void m_RotateLeft (Node *&curNode) {
Node *aux = curNode -> right;
curNode -> right = curNode -> right -> left;
aux -> left = curNode;
curNode = aux;
}
void m_RotateRight (Node *&curNode) {
Node *aux = curNode -> left;
curNode -> left = curNode -> left -> right;
aux -> right = curNode;
curNode = aux;
}
void m_Balance (Node *&curNode) {
if (curNode -> priority < curNode -> left -> priority) {
m_RotateRight (curNode);
}
else if (curNode -> priority < curNode -> right -> priority) {
m_RotateLeft (curNode);
}
m_UpdateHM (curNode -> left);
m_UpdateHM (curNode -> right);
}
void m_Insert (int value, int priority, int position, Node *&curNode) {
if (curNode == NILL) {
curNode = new Node (value, 1, priority, NILL, NILL);
return;
}
m_Propagate (curNode);
if (curNode -> left -> howMany + 1 >= position) {
m_Insert (value, priority, position, curNode -> left);
}
else {
m_Insert (value, priority, position - curNode -> left -> howMany - 1, curNode -> right);
}
m_Balance (curNode);
m_UpdateHM (curNode);
}
void m_Erase (int position, Node *&curNode) {
if (curNode == NILL) {
return;
}
if (curNode -> left -> howMany + 1 == position) {
if (curNode -> left == NILL and curNode -> right == NILL) {
delete curNode;
curNode = NILL;
return;
}
if (curNode -> left -> priority < curNode -> right -> priority) {
m_RotateLeft (curNode);
}
else {
m_RotateRight (curNode);
}
m_UpdateHM (curNode);
m_Erase (position, curNode);
}
else if (curNode -> left -> howMany >= position) {
m_Erase (position, curNode -> left);
}
else {
m_Erase (position - curNode -> left -> howMany - 1, curNode -> right);
}
m_Balance (curNode);
m_UpdateHM (curNode);
}
void m_Access (int position, Node *&curNode) {
m_Propagate (curNode);
if (curNode -> left -> howMany + 1 == position) {
fout << curNode -> value << '\n';
return;
}
if (curNode -> left -> howMany + 1 > position) {
m_Access (position, curNode -> left);
}
else {
m_Access (position - curNode -> left -> howMany - 1, curNode -> right);
}
}
void m_Split (int position, Node *&l, Node *&r) {
m_Insert (0, INF, position, R);
l = R -> left;
r = R -> right;
delete R;
R = NILL;
}
void m_Join (Node *&l, Node *&r) {
R = new Node (-1, l -> howMany + r -> howMany + 1, INF, l, r);
m_Erase (l -> howMany + 1, R);
}
void m_Reverse (int i, int j) {
Node *l, *m, *r;
m_Split (i, l, m);
R = m;
m_Split (j - i + 2, m, r);
m -> lazy = true;
m_Propagate (m);
m_Join (m, r);
m = R;
m_Join (l, m);
}
void m_Remove (int i, int j) {
Node *l, *m, *r;
m_Split (i, l, m);
R = m;
m_Split (j - i + 2, m, r);
delete m;
m_Join (l, r);
}
};
int main () {
srand (27);
Treap *t = new Treap ();
int n, k;
fin >> n >> k;
while (n --) {
char type;
fin >> type;
if (type == 'I') {
int value, position;
fin >> value >> position;
t -> Insert (value, position);
}
else if (type == 'A') {
int position;
fin >> position;
t -> Access (position);
}
else if (type == 'R') {
int i, j;
fin >> i >> j;
t -> Reverse (i, j);
}
else if (type == 'D') {
int i, j;
fin >> i >> j;
t -> Remove (i, j);
}
}
t -> Print ();
}