#include <bits/stdc++.h>
#define INF (1LL << 31) - 1
#define MAXBUF (1 << 17)
FILE *fi, *fout;
char buf[MAXBUF];
int pbuf = MAXBUF;
inline char nextch() {
if(pbuf == MAXBUF) {
fread(buf, 1, MAXBUF, fi);
pbuf = 0;
}
return buf[pbuf++];
}
inline int getnr() {
char ch = nextch();
while(!isdigit(ch))
ch = nextch();
int nr = 0;
while(isdigit(ch)) {
nr = nr * 10 + ch - '0';
ch = nextch();
}
return nr;
}
inline char getch() {
char ch = nextch();
while(!isalpha(ch))
ch = nextch();
return ch;
}
struct Treap {
Treap *left, *right;
int prio, sz;
int val;
bool lazy;
Treap(int _val,int _prio) {
left = right = NULL;
prio = _prio;
sz = 1;
val = _val;
lazy = 0;
}
};
Treap *T = NULL;
Treap *insert(Treap *, int , int , int );
Treap *balance(Treap *);
Treap *rot_left(Treap *);
Treap *rot_right(Treap *);
Treap *erase(Treap *, int );
std::pair <Treap * , Treap *> split(Treap *, int );
Treap *join(Treap *, Treap *);
inline Treap *reverse(Treap *, int , int );
inline int query(Treap *, int );
inline void refresh(Treap *);
void print(Treap *);
inline void prop(Treap *nod) {
if(nod -> left != NULL)
nod -> left -> lazy ^= nod -> lazy;
if(nod -> right != NULL)
nod -> right -> lazy ^= nod -> lazy;
}
inline void solve_lazy(Treap *nod) {
if(nod == NULL)
return ;
prop(nod);
if(nod -> lazy == 1)
std::swap(nod -> left , nod -> right);
nod -> lazy = 0;
}
Treap *insert(Treap *nod, int pos, int val,int prio) {
if(nod == NULL) {
nod = new Treap(val, prio);
return nod;
}
solve_lazy(nod);
if(nod -> left == NULL) {
if(pos == 0)
nod -> left = insert(nod -> left, pos, val, prio);
else
nod -> right = insert(nod -> right, pos - 1, val, prio);
}
else if(nod -> left -> sz >= pos)
nod -> left = insert(nod -> left, pos, val, prio);
else
nod -> right = insert(nod -> right, pos - nod -> left -> sz - 1, val, prio);
return balance(nod);
}
Treap *balance(Treap *nod) {
if(nod -> left != NULL && nod -> left -> prio > nod -> prio)
return rot_right(nod);
if(nod -> right != NULL && nod -> right -> prio > nod -> prio)
return rot_left(nod);
refresh(nod);
return nod;
}
Treap *rot_left(Treap *nod) {
Treap *aux = nod -> right;
solve_lazy(aux);
nod -> right = aux -> left;
aux -> left = nod;
refresh(nod);
refresh(aux);
return aux;
}
Treap *rot_right(Treap *nod) {
Treap *aux = nod -> left;
solve_lazy(aux);
nod -> left = aux -> right;
aux -> right = nod;
refresh(nod);
refresh(aux);
return aux;
}
Treap *erase(Treap *nod, int pos, bool flag) {
solve_lazy(nod);
if((nod -> left == NULL && pos == 1) || (nod -> left != NULL && nod -> left -> sz + 1 == pos) || flag == 1) {
Treap *aux;
if(nod -> left == NULL && nod -> right == NULL) {
delete nod;
return NULL;
}
else if(nod -> left == NULL) {
aux = rot_left(nod);
aux -> left = erase(aux -> left, pos, 1);
}
else if(nod -> right == NULL) {
aux = rot_right(nod);
aux -> right = erase(aux -> right, pos, 1);
}
else if(nod -> left -> prio > nod -> right -> prio) {
aux = rot_right(nod);
aux -> right = erase(aux -> right, pos, 1);
}
else {
aux = rot_left(nod);
aux -> left = erase(aux -> left, pos, 1);
}
return balance(aux);
}
else {
if(nod -> left == NULL)
nod -> right = erase(nod -> right, pos - 1, 0);
else if(nod -> left -> sz >= pos)
nod -> left = erase(nod -> left, pos, 0);
else
nod -> right = erase(nod -> right, pos - nod -> left -> sz - 1, 0);
return balance(nod);
}
}
std::pair <Treap * , Treap *> split(Treap *nod, int pos) {
solve_lazy(nod);
nod = insert(nod, pos - 1, -1, INF);
std::pair <Treap * , Treap *> ans = std::make_pair(nod -> left , nod -> right);
delete nod;
nod = NULL;
return ans;
}
Treap *join(Treap *nod1, Treap *nod2) {
solve_lazy(nod1);
solve_lazy(nod2);
Treap *nod = new Treap(-1, 0);
nod -> left = nod1;
nod -> right = nod2;
if(nod -> left == NULL)
nod = erase(nod, 1, 0);
else
nod = erase(nod, nod -> left -> sz + 1, 0);
return nod;
}
Treap *solve(Treap *nod, int l, int r) {
solve_lazy(nod);
std::pair <Treap * , Treap *> aux1 = split(nod, l);
std::pair <Treap * , Treap *> aux2 = split(aux1.second, r - l + 2);
return join(aux1.first, aux2.second);
}
inline Treap *reverse(Treap *nod, int l, int r) {
solve_lazy(nod);
std::pair <Treap * , Treap *> aux1 = split(nod, l);
std::pair <Treap * , Treap *> aux2 = split(aux1.second, r - l + 2);
aux2.first -> lazy ^= 1;
return join(join(aux1.first, aux2.first), aux2.second);
}
inline int query(Treap *nod, int pos) {
solve_lazy(nod);
if((nod -> left == NULL && pos == 1) || (nod -> left != NULL && nod -> left -> sz + 1 == pos))
return nod -> val;
if(nod -> left == NULL)
return query(nod -> right, pos - 1);
else if(nod -> left -> sz >= pos)
return query(nod -> left, pos);
else
return query(nod -> right, pos - nod -> left -> sz - 1);
}
inline void refresh(Treap *nod) {
nod -> sz = 1;
if(nod -> left != NULL)
nod -> sz += nod -> left -> sz;
if(nod -> right != NULL)
nod -> sz += nod -> right -> sz;
}
void print(Treap *nod) {
if(nod == NULL)
return ;
solve_lazy(nod);
print(nod -> left);
fprintf(fout,"%d " ,nod -> val);
print(nod -> right);
}
int main() {
int n, pos, val, l, r, k;
fi = fopen("secv8.in" ,"r");
fout = fopen("secv8.out" ,"w");
srand(time(NULL));
n = getnr();
k = getnr();
while(n > 0) {
n--;
char ch;
ch = getch();
if(ch == 'I') {
pos = getnr();
val = getnr();
T = insert(T, pos - 1, val, rand());
}
if(ch == 'A') {
pos = getnr();
fprintf(fout,"%d\n" ,query(T, pos));
}
if(ch == 'R') {
l = getnr();
r = getnr();
T = reverse(T, l, r);
}
if(ch == 'D') {
l = getnr();
r = getnr();
T = solve(T, l, r);
}
}
print(T);
fclose(fi);
fclose(fout);
return 0;
}