#include <bits/stdc++.h>
using namespace std;
ifstream in("secv8.in");
ofstream out("secv8.out");
const int NMAX = 250000;
typedef struct Treap* Arbore;
typedef pair<Arbore, Arbore> PAA;
Arbore NIL;
struct Treap
{
int g, lazy, prio, val;
Treap *st, *dr;
Treap(int _val) : g(1), lazy(0), prio(rand()), val(_val), st(NIL), dr(NIL) {}
~Treap() {
if ( st != NIL ) delete st;
if ( dr != NIL ) delete dr;
}
};
PAA split(Arbore x, int poz);
Arbore join(Arbore a, Arbore b);
void recalc(Arbore x)
{
x->g = x->st->g + x->dr->g + (x != NIL);
}
void my_lazy(Arbore x)
{
if (x->lazy) {
swap(x->st, x->dr);
x->st->lazy ^= 1;
x->dr->lazy ^= 1;
/// recalc(x);
}
x->lazy = 0;
}
void AFIS(Arbore x) {
my_lazy(x);
if( x == NIL ) return;
AFIS(x->st);
out << x->val << ' ';
AFIS(x->dr);
}
Arbore T_insert(Arbore ROOT, int val, int poz)
{
Arbore tr = new Treap(val);
PAA pr = split(ROOT, poz);
return join( join(pr.first, tr), pr.second );
}
Arbore T_reverse(Arbore ROOT, int x, int y)
{
PAA p1 = split(ROOT, y+1);
PAA p2 = split(p1.first, x);
p2.second->lazy ^= 1;
return join( join(p2.first, p2.second), p1.second );
}
Arbore T_delete(Arbore ROOT, int x, int y)
{
PAA p1 = split(ROOT, y+1);
PAA p2 = split(p1.first, x);
delete p2.second;
return join(p2.first, p1.second);
}
int T_elem(Arbore x, int poz)
{
my_lazy(x);
if (x->st->g == poz - 1)
return x->val;
if (x->st->g >= poz)
return T_elem(x->st, poz);
return T_elem(x->dr, poz - x->st->g - 1);
}
int main()
{
NIL = new Treap(0);
NIL->g = 0;
NIL->st = NIL->dr = NIL;
srand(time(0));
Arbore ROOT = NIL;
int N, useless;
in >> N >> useless;
while(N--) {
char ch;
int x,y;
in >> ch >> x;
if ( ch == 'I' )
in >> y,
ROOT = T_insert(ROOT, y,x); /// Treap, val, poz
else if (ch == 'A')
out << T_elem(ROOT, x) << '\n'; /// Treap, poz
else if (ch == 'R')
in >> y,
ROOT = T_reverse(ROOT, x,y); /// Treap, rot x-y
else if (ch == 'D')
in >> y,
ROOT = T_delete(ROOT, x,y); /// Treap, del x-
}
AFIS(ROOT);
return 0;
}
PAA split(Arbore a, int poz) {
my_lazy(a);
if( poz > a->g ) return {a, NIL};
if( poz == a->st->g+1 ) {
PAA ans = {a->st, a};
a->st = NIL;
recalc(a);
return ans;
}
if( poz <= a->st->g ) {
PAA ans = split( a->st, poz );
a->st = NIL;
recalc(a);
return {ans.first, join(ans.second, a)};
}
PAA ans = split( a->dr, poz - a->st->g - 1 );
a->dr = NIL;
recalc( a );
return { join(a, ans.first), ans.second };
}
Arbore join(Arbore a, Arbore b)
{
my_lazy(a);
my_lazy(b);
if (a == NIL)
return b;
if (b == NIL)
return a;
if (a->prio > b->prio) {
a->dr = join(a->dr, b);
recalc(a);
return a;
}
b->st = join( a, b->st );
recalc(b);
return b;
}