#include <bits/stdc++.h>
using namespace std;
ifstream fi( "secv8.in" );
ofstream fo( "secv8.out");
struct Treap {
int key, prio, sz, rev;
Treap *left, *right;
} *nil;
Treap *root;
void update( Treap *node ) {
node->sz = node->left->sz + node->right->sz + 1;
}
void propagation( Treap *node ) {
if (!node->rev)
return;
swap( node->left, node->right );
node->rev ^= 1;
node->left->rev ^= 1;
node->right->rev ^= 1;
}
Treap *join( Treap *f, Treap *s ) {
if (f == nil)
return s;
if (s == nil)
return f;
propagation( f ), propagation( s );
if (f->prio >= s->prio) {
f->right = join( f->right, s );
update( f );
return f;
}
s->left = join( f, s->left );
update( s );
return s;
}
pair < Treap*, Treap* > split( Treap *node, const int pos ) {
if (node == nil)
return { nil, nil };
propagation( node );
if (node->left->sz == pos) {
Treap *aux = node->left;
node->left = nil;
update( node );
return { aux, node };
}
if (node->left->sz > pos) {
auto aux = split( node->left, pos );
node->left = aux.second;
update( node );
aux.second = node;
return aux;
}
auto aux = split( node->right, pos - node->left->sz - 1 );
node->right = aux.first;
update( node );
aux.first = node;
return aux;
}
Treap *insert( Treap *root, int pos, int key ) {
Treap *node = new Treap();
node->key = key, node->prio = rand(), node->sz = 1, node->rev = 0;
node->left = node->right = nil;
auto aux = split( root, pos );
return join( join( aux.first, node ), aux.second );
}
int access( Treap *node, int pos ) {
propagation( node );
if (node->left->sz == pos)
return node->key;
if (node->left->sz > pos)
return access( node->left, pos );
return access( node->right, pos - node->left->sz - 1 );
}
Treap *reverse( Treap *node, int left, int right ) {
auto aux0 = split( node, left-1 );
auto aux1 = split( aux0.second, right );
aux1.first->rev ^= 1;
return join( aux0.first, join( aux1.first, aux1.second ) );
}
Treap *erase( Treap *node, int left, int right ) {
auto aux0 = split( node, left-1 );
auto aux1 = split( aux0.second, right - left + 1 );
return join( aux0.first, aux1.second );
}
void dfs( Treap *node ) {
if (node == nil)
return;
propagation( node );
dfs( node->left );
fo << node->key << " ";
dfs( node->right );
}
int main()
{
srand( time( 0 ) );
int queries, r, pos, key, left, right;
char ch;
nil = new Treap();
*nil = {0, -1, 0, 0, nil, nil };
root = nil;
fi >> queries >> r;
while (queries--) {
fi >> ch;
switch(ch) {
case 'I': {
fi >> pos >> key;
root = insert( root, pos-1, key );
break;
}
case 'A': {
fi >> pos;
fo << access( root, pos-1 ) << '\n';
break;
}
case 'R': {
fi >> left >> right;
root = reverse( root, left, right );
break;
}
case 'D': {
fi >> left >> right;
root = erase( root, left, right );
break;
}
}
//dfs( root );
//fo << '\n';
}
dfs( root );
return 0;
}