#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;
class Node {
public:
int val;
int priority; // max heap
int size;
int sum;
bool reversed;
Node *lson;
Node *rson;
};
Node *emptyNode = new Node{-1, -1, 0, 0, false, NULL, NULL};
inline void computeSize(Node *root) {
if(root != emptyNode)
root->size = 1 + root->lson->size + root->rson->size;
}
void propagate(Node* &root) {
if(root == emptyNode)
return ;
if(root->reversed == true) {
root->reversed = false;
root->lson->reversed ^= 1;
root->rson->reversed ^= 1;
Node *aux = root->lson;
root->lson = root->rson;
root->rson = aux;
}
}
void split(Node* root, int k, Node* &first, Node* &second) {
propagate(root);
if(root == emptyNode) {
first = second = emptyNode;
} else if(k <= root->lson->size) {
split(root->lson, k, first, root->lson);
second = root;
computeSize(second);
} else {
split(root->rson, k - root->lson->size - 1, root->rson, second);
first = root;
computeSize(first);
}
}
void Merge(Node* &root, Node* first, Node* second) {
if(first == emptyNode) {
root = second;
return;
} else if(second == emptyNode) {
root = first;
return;
}
propagate(first);
propagate(second);
if(first->priority < second->priority) {
Merge(second->lson, first, second->lson);
root = second;
} else {
Merge(first->rson, first->rson, second);
root = first;
}
computeSize(root);
}
void Insert(Node* &root, int value, int priority, int k) {
propagate(root);
if(priority > root->priority) {
Node *first = new Node{value, priority, 0, 0, NULL, NULL};
split(root, k - 1, first->lson, first->rson);
root = first;
computeSize(root);
return ;
}
if(k <= root->lson->size + 1)
Insert(root->lson, value, priority, k);
else
Insert(root->rson, value, priority, k - root->lson->size - 1);
computeSize(root);
}
int Erase(Node* &root, int k) {
Node *first, *second, *third;
split(root, k - 1, first, second);
split(second, 1, second, third);
Merge(root, first, third);
int aux = second->val;
delete second;
return aux;
}
void EraseInterval(Node* &root, int st, int dr) {
Node *first, *second, *third;
split(root, st - 1, first, second);
split(second, dr - st + 1, second, third);
Merge(root, first, third);
delete second;
}
void ReverseInterval(Node* &root, int st, int dr) {
Node *first, *second, *third;
split(root, st - 1, first, second);
split(second, dr - st + 1, second, third);
second->reversed = true;
Merge(root, first, second);
Merge(root, root, third);
}
int access(Node* &root, int k) {
if(root == emptyNode)
return -1;
propagate(root);
int posRoot = root->lson->size + 1;
if(k < posRoot)
return access(root->lson, k);
else if(k == posRoot)
return root->val;
else
return access(root->rson, k - posRoot);
}
void afis(Node *root) {
if(root == emptyNode)
return ;
propagate(root);
afis(root->lson);
printf("%d ", root->val);
afis(root->rson);
}
int main() {
freopen("secv8.in", "r", stdin);
freopen("secv8.out", "w", stdout);
int N, nrnefolositor;
scanf("%d %d\n", &N, &nrnefolositor);
srand(time(0));
Node *root = emptyNode;
for(int i = 1; i <= N; ++ i) {
char op;
op = getc(stdin);
switch(op) {
case 'I': {
int k, e; /// pos si val
scanf(" %d %d\n", &k, &e);
Insert(root, e, rand(), k);
break;
}
case 'R': {
int st, dr;
scanf(" %d %d\n", &st, &dr);
ReverseInterval(root, st, dr);
break;
}
case 'A': {
int pos;
scanf(" %d\n", &pos);
printf("%d\n", access(root, pos));
break;
}
case 'D': {
int st, dr;
scanf(" %d %d\n", &st, &dr);
EraseInterval(root, st, dr);
break;
}
}
}
afis(root);
return 0;
}