#include <bits/stdc++.h>
using namespace std;
FILE *fi, *fout;
const int INF = 2e9;
struct Treap {
Treap *left, *right;
int val, prio;
int sz;
bool lazy;
Treap(int _val, int _prio) {
left = right = NULL;
sz = 1;
val = _val;
prio = _prio;
lazy = 0;
}
};
Treap *root = NULL;
Treap *balance(Treap *);
inline void refresh(Treap *);
inline void solve_lazy(Treap *nod) {
if(nod == NULL)
return ;
if(nod -> lazy) {
swap(nod -> left, nod -> right);
if(nod -> left != NULL)
nod -> left -> lazy ^= 1;
if(nod -> right != NULL)
nod -> right -> lazy ^= 1;
}
nod -> lazy = 0;
}
Treap *insert(Treap *nod, int pos, int val, int prio) {
solve_lazy(nod);
if(nod == NULL) {
nod = new Treap(val, prio);
return 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(pos <= nod -> left -> sz)
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 *rot_left(Treap *nod) {
solve_lazy(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) {
solve_lazy(nod);
Treap *aux = nod -> left;
solve_lazy(aux);
nod -> left = aux -> right;
aux -> right = nod;
refresh(nod);
refresh(aux);
return aux;
}
Treap *balance(Treap *nod) {
solve_lazy(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 *erase(Treap *nod, int pos, bool flag) {
solve_lazy(nod);
if((pos == 1 && nod -> left == NULL) || (nod -> left != NULL && nod -> left -> sz + 1 == pos) || flag) {
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);
}
}
pair <Treap*, Treap*> split(Treap *nod, int pos) {
solve_lazy(nod);
Treap *aux = insert(nod, pos, 0, INF);
return {aux -> left, aux -> right};
}
Treap *join(Treap *nod1, Treap *nod2) {
solve_lazy(nod1);
solve_lazy(nod2);
Treap *aux = new Treap(0, INF);
aux -> left = nod1;
aux -> right = nod2;
if(aux -> left == NULL)
aux = erase(aux, 1, 0);
else
aux = erase(aux, aux -> left -> sz + 1, 0);
return aux;
}
Treap *rev(Treap *nod, int l, int r) {
solve_lazy(nod);
pair <Treap*, Treap*> aux1 = split(nod, l - 1);
pair <Treap*, Treap*> aux2 = split(aux1.second, r - l + 1);
if(aux2.first != NULL)
aux2.first -> lazy ^= 1;
return join(join(aux1.first, aux2.first), aux2.second);
}
Treap *del(Treap *nod, int l, int r) {
solve_lazy(nod);
pair <Treap*, Treap*> aux1 = split(nod, l - 1);
pair <Treap*, Treap*> aux2 = split(aux1.second, r - l + 1);
return join(aux1.first, aux2.second);
}
int acces(Treap *nod, int pos) {
solve_lazy(nod);
if((nod -> left == NULL && pos == 1) || (nod -> left != NULL && pos == nod -> left -> sz + 1)) {
return nod -> val;
}
else {
if(nod -> left == NULL) {
return acces(nod -> right, pos - 1);
}
else {
if(nod -> left -> sz >= pos)
return acces(nod -> left, pos);
else
return acces(nod -> right, pos - nod -> left -> sz - 1);
}
}
}
inline void refresh(Treap *nod) {
solve_lazy(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);
//printf("%d " ,nod -> val);
fprintf(fout,"%d " ,nod -> val);
print(nod -> right);
}
int main() {
int q, t;
fi = fopen("secv8.in" ,"r");
fout = fopen("secv8.out" ,"w");
srand(time(NULL));
fscanf(fi,"%d %d " ,&q,&t);
while(q > 0) {
q--;
int pos, val, l, r;
char ch;
fscanf(fi,"%c " ,&ch);
if(ch == 'I') {
fscanf(fi,"%d %d " ,&pos,&val);
root = insert(root, pos - 1, val, rand());
}
if(ch == 'A') {
fscanf(fi,"%d " ,&pos);
fprintf(fout,"%d\n" ,acces(root, pos));
}
if(ch == 'R') {
fscanf(fi,"%d %d " ,&l,&r);
root = rev(root, l, r);
}
if(ch == 'D') {
fscanf(fi,"%d %d " ,&l,&r);
root = del(root, l, r);
}
// print(root);
// printf("\n");
}
print(root);
fclose(fi);
fclose(fout);
return 0;
}