#include <cstdio>
#include <cstdlib>
#include <ctime>
const int inf = 2000000000;
using namespace std;
struct treap {
int key, prior, din, rev, val;
treap *left, *right;
};
int n, er;
int i, j, poz, nr, poz1, poz2;
treap *R, *nil;
char ch;
treap *rotate_left(treap *nod) {
treap *aux;
aux = nod->right;
nod->right = aux->left;
aux->left = nod;
nod->din = nod->left->din + nod->right->din + 1;
return aux;
}
treap *rotate_right(treap *nod) {
treap *aux;
aux = nod->left;
nod->left = aux->right;
aux->right = nod;
nod->din = nod->left->din + nod->right->din + 1;
return aux;
}
treap *insert(treap *nod, int poz, int val, int pr) {
if (nod == nil) {
nod = new treap;
nod->val = val;
nod->prior = pr;
nod->din = 1;
nod->rev = 0;
nod->left = nod->right = nil;
return nod;
}
if (poz <= nod->left->din + 1 || (nod->din == 1 && poz <= 1)) {
nod->left = insert(nod->left, poz, val, pr);
if (nod->left->prior > nod->prior)
nod = rotate_right(nod);
}
else {
nod->right = insert(nod->right, poz - nod->left->din - 1, val, pr);
if (nod->right->prior > nod->prior)
nod = rotate_left(nod);
}
nod->din = nod->left->din + nod->right->din + 1;
// fprintf(stderr, "%d %d %d\n", nod->din, nod->left->din, nod->right->din);
// fprintf(stderr, "%d %d %d %d %d %d %d\n", poz, nod->din, nod->val, nod->left->din, nod->left->val, nod->right->din, nod->right->val);
return nod;
}
treap *access(treap *nod, int poz, int r) {
// fprintf(stderr, "%d %d %d %d %d %d %d %d\n", poz, r, nod->din, nod->val, nod->left->din, nod->left->val, nod->right->din, nod->right->val);
if (nod->left->din + 1 == poz)
return nod;
if (poz <= nod->left->din)
return access(nod->left, poz, nod->left->rev ^ r);
else
return access(nod->right, poz - nod->left->din - 1, nod->right->rev ^ r);
}
void split(treap *nod, int poz, treap *&nod1, treap *&nod2) {
treap *aux;
aux = insert(nod, poz, 0, inf);
nod1 = aux->left;
nod2 = aux->right;
}
treap *erase(treap *nod) {
if (nod->left == nil && nod->right == nil) {
delete nod;
nod = nil;
return nod;
}
if (nod->left->prior > nod->right->prior) {
nod = rotate_right(nod);
nod->right = erase(nod->right);
}
else {
nod = rotate_left(nod);
nod->left = erase(nod->left);
}
nod->din = nod->left->din + nod->right->din + 1;
return nod;
}
treap *join(treap *nod1, treap *nod2) {
treap *aux;
aux = new treap;
*aux = *nil;
// aux->val = aux->prior = 0;
aux->left = nod1; aux->right = nod2;
aux->din = nod1->din + nod2->din + 1;
// fprintf(stderr, "Inainte de erase\n");
erase(aux);
}
treap *_delete(treap *nod, int p1, int p2) {
treap *t1, *t2, *t3, *t4;
split(nod, p1, t1, t2);
split(t2, p2 + 2 - p1, t3, t4);
// fprintf(stderr, "trece de split\n");
nod = join(t1, t4);
return nod;
}
treap *reverse(treap *nod, int p1, int p2) {
treap *t1, *t2, *t3, *t4, *aux;
split(nod, p1, t1, t2);
split(t2, p2 + 1, t3, t4);
t3->rev = 1 ^ t3->rev;
nod = join(t3, t4);
nod = join(t1, nod);
return nod;
}
void parc_fin(treap *nod) {
if (nod == nil)
return;
parc_fin(nod->left);
printf("%d ", nod->val);
parc_fin(nod->right);
}
int main() {
freopen("secv8.in", "r", stdin);
freopen("secv8.out", "w", stdout);
srand(time(0));
nil = new treap;
nil->val = nil->prior = nil->key = nil->din = nil->rev = 0;
R = nil;
scanf("%d%d", &n, &er);
for (i = 1; i <= n; i++) {
scanf(" %c ", &ch);
// fprintf(stderr, "%d\n", i);
if (ch == 'I') {
scanf("%d%d", &poz, &nr);
int pr = rand() % 100000 + 1;
R = insert(R, poz, nr, pr);
}
if (ch == 'A') {
scanf("%d", &poz);
printf("%d\n", access(R, poz, 0)->val);
}
if (ch == 'R') {
scanf("%d%d", &poz1, &poz2);
// R = reverse(R, poz1, poz2);
}
if (ch == 'D') {
scanf("%d%d", &poz1, &poz2);
// fprintf(stderr, "%d\n", i);
R = _delete(R, poz1, poz2);
}
}
parc_fin(R);
return 0;
}