#include <fstream>
#include <ctime>
#define INF 2000000000
using namespace std;
ifstream fin ("secv8.in");
ofstream fout ("secv8.out");
struct treap{
int val;
int priority;
int nr; /// cate nr am in secv
int lazy; /// daca trb sau nu inversat
treap *left;
treap *right;
treap (int val, int priority, int nr, int lazy, treap *left, treap *right){
this->val = val;
this->priority = priority;
this->nr = nr;
this->lazy = lazy;
this->left = left;
this->right = right;
}
};
treap *rad,*rad_aux,*rad_left,*rad_right,*nil;
int get_rand (){
return 1LL*rand()*rand()%(INF-1)+1;
}
void update (treap *&rad){
if (rad == nil)
rad->nr = 0;
else {
rad->nr = rad->left->nr + rad->right->nr + 1;
/// acum lazy ul
if (rad->lazy){
rad->left->lazy = 1-rad->left->lazy;
rad->right->lazy = 1-rad->right->lazy;
/// acum trebuie sa interschimb fiii
swap (rad->left,rad->right);
rad->lazy = 0;
}}}
void rotate_right (treap *&rad){
treap *aux = rad->left;
rad->left = aux->right;
aux->right = rad;
rad = aux;
update (rad->right);
update (rad);
}
void rotate_left (treap *&rad){
treap *aux = rad->right;
rad->right = aux->left;
aux->left = rad;
rad = aux;
update (rad->left);
update (rad);
}
void balance (treap *&rad){
if (rad->left != nil && rad->left->priority > rad->priority)
rotate_right (rad);
else {
if (rad->right != nil && rad->right->priority > rad->priority)
rotate_left (rad);
}
//update (rad);
}
void _insert (treap *&rad, int poz, int val, int priority){
if (rad == nil)
rad = new treap (val,priority,1,0,nil,nil);
else {
if (rad->left->nr + 1 >= poz) /// ma duc in stanga
_insert (rad->left,poz,val,priority);
else _insert (rad->right,poz - rad->left->nr - 1,val,priority);
balance (rad);
rad->nr = rad->left->nr + rad->right->nr + 1;
}}
void _delete (treap *&rad, int val){
if (rad->left == nil && rad->right == nil){
if (rad->val == val){
delete rad;
rad = nil;
}
} else {
update (rad);
if (rad->left->priority > rad->right->priority){
update (rad->left);
rotate_right (rad);
_delete (rad->right,val);
} else {
update (rad->right);
rotate_left (rad);
_delete (rad->left,val);
}
update (rad);
}}
int access (treap *&rad, int nr){
update (rad);
if (rad->left->nr == nr-1)
return rad->val;
if (rad->left->nr >= nr)
return access (rad->left,nr);
return access (rad->right,nr - rad->left->nr - 1);
}
void join (treap *&rad, treap *rad1, treap *rad2){
/// adaug o radacina fictiva
treap *aux = new treap (INF,-1,rad1->nr + rad2->nr,0,rad1,rad2);
rad = aux;
_delete (rad,INF);
}
void split (treap *rad, treap *&rad1, treap *&rad2, int poz){
/// vreau sa despart treapul in doua
/// inserez un nod care va deveni radacina si cei doi fii vor fi exact treapurile
_insert (rad,poz,INF,INF);
rad1 = rad->left;
rad2 = rad->right;
delete rad;
}
void dfs (treap *rad){
if (rad == nil)
return;
update (rad);
dfs (rad->left);
fout<<rad->val<<" ";
dfs (rad->right);
}
int main (){
srand (time(0));
rad = nil = new treap (0,0,0,0,NULL,NULL);
int t,ok,k,x,y;
fin>>t>>ok;
for (;t--;){
char op;
fin>>op;
if (op == 'I'){
fin>>k>>x;
_insert (rad,k,x,get_rand()%INF);
continue;
}
if (op == 'A'){
fin>>x;
fout<<access (rad,x)<<"\n";
continue;
}
if (op == 'R'){
fin>>x>>y;
/// trb sa intorc sirul de la i la j => trb sa fac lazy update
/// mai intai dau split ca sa aflu bucata
split (rad,rad_aux,rad_right,y+1);
split (rad_aux,rad_left,rad,x); /// acum in rad ramane bucata care trebuie inversata
rad->lazy = 1;
/// acum le dau join sa le unesc pe toate trei la loc
join (rad_aux,rad_left,rad);
join (rad,rad_aux,rad_right);
continue;
}
/// acum trebuie sa sterg o secventa
fin>>x>>y;
/// dau split de doua ori si dupa unesc doar cele doua bucati
split (rad,rad_aux,rad_right,y+1);
split (rad_aux,rad_left,rad,x);
join (rad,rad_left,rad_right);
}
dfs (rad);
return 0;
}