#include <cstdio>
#include <cstdlib>
#include <time.h>
typedef struct _Treap {
_Treap *l, *r;
int size, key;
int pr;
bool lazy;
_Treap(int val) {
l = r = NULL;
key = val;
pr = rand() ^ rand();
size = 1;
lazy = false;
}
~_Treap() { delete l; delete r; }
void recalc() {
size = 1;
prop();
if(l != NULL) size = size + l -> size;
if(r != NULL) size = size + r -> size;
}
void prop() {
if(lazy == true) {
_Treap *aux;
lazy = false;
aux = l;
l = r;
r = aux;
if(l != NULL) l -> lazy ^= 1;
if(r != NULL) r -> lazy ^= 1;
}
}
} *Treap;
void recalc(Treap x) {
if(x != NULL) x -> recalc();
}
Treap join(Treap l, Treap r) {
if(l != NULL) recalc(l);
if(r != NULL) recalc(r);
if(l == NULL) return r;
if(r == NULL) return l;
if(l -> pr < r -> pr) {
l -> r = join(l -> r, r);
recalc(l);
return l;
} else {
r -> l = join(l, r -> l);
recalc(r);
return r;
}
}
int getSize(Treap x) {
if(x == NULL)
return 0;
recalc(x);
return x -> size;
}
void split(Treap t, int x, Treap &l, Treap &r, int extra) {
int poz;
recalc(t);
l = r = NULL;
if(t == NULL) return;
poz = extra + getSize(t -> l) + 1;
if(poz < x) {
split(t -> r, x, t -> r, r, poz);
l = t;
} else {
split(t -> l, x, l, t -> l, extra);
r = t;
}
recalc(t);
}
Treap add(Treap t, int poz, int key) {
Treap l, r;
recalc(t);
split(t, poz, l, r, 0);
return join(join(l, new _Treap(key)), r);
}
bool dodebug = false;
void debug(Treap x, int space, int extra) {
int poz;
if(dodebug) {
if(x == NULL)
printf("(null)\n");
else if(x -> l == NULL && x -> r == NULL) {
//x -> prop();
poz = 1 + extra + getSize(x -> l);
for(int i = 0; i < space; ++i)
printf(" ");
printf("%d %d %d %d\n", poz, x -> key, x -> lazy, x->pr);
} else {
//x -> prop();
poz = 1 + extra + getSize(x -> l);
for(int i = 0; i < space; ++i)
printf(" ");
printf("%d %d %d %d\n", poz, x -> key, x->lazy, x->pr);
if(x->l != NULL) {
for(int i = 0; i < space; ++i)
printf(" ");
printf("left:\n");
debug(x -> l, space + 2, extra);
}
if(x->r != NULL) {
for(int i = 0; i < space; ++i)
printf(" ");
printf("right:\n");
debug(x -> r, space + 2, poz);
}
}
}
}
Treap erase(Treap t, int poz, int poz2) {
Treap l, r, p;
split(t, poz2 + 1, p, r, 0);
split(p, poz, l, p, 0);
delete p;
return join(l, r);
}
int acces(Treap t, int k, int extra) {
int poz;
if(t == NULL) {
printf("BELIT-AI PULA\n");
return -1;
}
recalc(t);
poz = extra + getSize(t -> l) + 1;
if(poz == k)
return t -> key;
else if(poz < k)
return acces(t -> r, k, poz);
else
return acces(t -> l, k, extra);
}
/*bool check(Treap t, int val) {
if(t == NULL)
return false;
if(t -> key == val)
return true;
else if(val < t -> key)
return check(t -> l, val);
else
return check(t -> r, val);
}*/
Treap reverse(Treap t, int p1, int p2) {
Treap l, mid, r;
split(t, p2 + 1, mid, r, 0);
split(mid, p1, l, mid, 0);
mid -> lazy = true;
recalc(mid);
return join(join(l, mid), r);
}
int main() {
int n, bit, k, e, p1, p2;
char ch;
srand(time(NULL));
Treap x;
x = NULL;
FILE *fin = fopen("secv8.in", "r");
FILE *fout = fopen("secv8.out", "w");
fscanf(fin, "%d%d\n", &n, &bit);
for(int i = 0; i < n; ++i) {
ch = fgetc(fin);
while(ch == ' ' || ch == '\n')
ch = fgetc(fin);
if(ch == 'I') {
fscanf(fin, "%d%d", &k, &e);
x = add(x, k, e);
} else if(ch == 'A') {
fscanf(fin, "%d", &k);
fprintf(fout, "%d\n", acces(x, k, 0));
} else if(ch == 'R') {
fscanf(fin, "%d%d", &p1, &p2);
x = reverse(x, p1, p2);
} else {
fscanf(fin, "%d%d", &p1, &p2);
x = erase(x, p1, p2);
}
}
n = getSize(x);
for(int i = 1; i <= n; ++i) {
fprintf(fout, "%d ", acces(x, i, 0));
}
fclose(fin);
fclose(fout);
return 0;
}
//sper ca acum ca am bagat treapurile sa fiu acceptat in societate