#include <bits/stdc++.h>
using namespace std;
template< class TYPE >
class nrxPositionTreap {
private:
int treapSize = 0;
static const int CONST1 = 29;
static const int CONST2 = 31;
static const int MOD1 = 666013;
static const int MOD2 = 666019;
static const int MAXSIZE = 200005;
vector< pair<int, int> > myHash;
struct treapNode {
TYPE key, minim, maxim, first, last; int nodeSize, priority;
pair <int, int> nodeHash; bool reversed;
treapNode *leftNode;
treapNode *rightNode;
treapNode() {
this -> nodeSize = 0; this -> nodeHash = make_pair( 0, 0 ); this -> priority = INT_MIN; this -> reversed = false;
this -> minim = this -> key; this -> maxim = this -> key; this -> first = this -> key; this -> last = this -> key;
this -> leftNode = NULL;
this -> rightNode = NULL;
}
treapNode( TYPE key, int nodeSize, int priority, pair <int, int> nodeHash, treapNode *leftNode, treapNode *rightNode ) {
this -> key = key; this -> nodeSize = nodeSize; this -> priority = priority; this -> nodeHash = nodeHash;
this -> minim = key; this -> maxim = key; this -> first = key; this -> last = key; this -> reversed = false;
this -> leftNode = leftNode;
this -> rightNode = rightNode;
}
} *root, *emptyNode;
void updateSize( treapNode *&node ) {
node -> nodeSize = 1 + node -> leftNode -> nodeSize + node -> rightNode -> nodeSize;
return;
}
void updateHash( treapNode *&node ) {
node -> nodeHash.first = (int) ( ( node -> rightNode -> nodeHash.first +
myHash[ node -> rightNode -> nodeSize + 1 ].first +
node -> leftNode -> nodeHash.first * 1LL * myHash[ node -> rightNode -> nodeSize + 2 ].first ) % MOD1 );
node -> nodeHash.second = (int) ( ( node -> rightNode -> nodeHash.second +
myHash[ node -> rightNode -> nodeSize + 1 ].second +
node -> leftNode -> nodeHash.second * 1LL * myHash[ node -> rightNode -> nodeSize + 2 ].second ) % MOD2 );
return;
}
void updateMinMax( treapNode *&node ) {
node -> minim = node -> key;
if( node -> leftNode != emptyNode ) node -> minim = min( node -> minim, node -> leftNode -> minim );
if( node -> rightNode != emptyNode ) node -> minim = min( node -> minim, node -> rightNode -> minim );
node -> maxim = node -> key;
if( node -> leftNode != emptyNode ) node -> maxim = max( node -> maxim, node -> leftNode -> maxim );
if( node -> rightNode != emptyNode ) node -> maxim = max( node -> maxim, node -> rightNode -> maxim );
return;
}
void updateFirstLast( treapNode *&node ) {
node -> first = ( ( node -> leftNode == emptyNode ) ? node -> key : node -> leftNode -> first );
node -> last = ( ( node -> rightNode == emptyNode ) ? node -> key : node -> rightNode -> last );
return;
}
void updateReverse( treapNode *&node ) {
if( node -> reversed == true ) {
swap( node -> leftNode, node -> rightNode ); node -> reversed = false;
if( node -> leftNode != emptyNode )
node -> leftNode -> reversed = !( node -> leftNode -> reversed );
if( node -> rightNode != emptyNode )
node -> rightNode -> reversed = !( node -> rightNode -> reversed );
}
}
void updateValues( treapNode *&node ) {
updateReverse( node );
updateSize( node );
updateHash( node );
updateMinMax( node );
updateFirstLast( node );
}
void rotateLeft( treapNode *&node ) {
updateValues( node );
updateValues( node -> leftNode );
treapNode *auxNode = node -> leftNode;
node -> leftNode = auxNode -> rightNode;
auxNode -> rightNode = node; node = auxNode;
updateValues( node -> rightNode );
updateValues( node );
return;
}
void rotateRight( treapNode *&node ) {
updateValues( node );
updateValues( node -> rightNode );
treapNode *auxNode = node -> rightNode;
node -> rightNode = auxNode -> leftNode;
auxNode -> leftNode = node; node = auxNode;
updateValues( node -> leftNode );
updateValues( node );
return;
}
void balanceNode( treapNode *&node ) {
updateReverse( node );
if( node -> leftNode -> priority > node -> priority )
rotateLeft( node );
if( node -> rightNode -> priority > node -> priority )
rotateRight( node );
return;
}
TYPE findKey( treapNode *&node, int position ) {
updateReverse( node );
if( node == emptyNode )
return node -> key;
if( node -> leftNode -> nodeSize + 1 == position )
return node -> key;
if( node -> leftNode -> nodeSize + 1 > position )
return findKey( node -> leftNode, position );
else
return findKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ) );
}
bool insertKey( treapNode *&node, int position, TYPE key, int priority ) {
bool ok; updateReverse( node );
if( node == emptyNode ) {
if( position != 1 )
return false;
node = new treapNode( key, 1, priority, myHash[1], emptyNode, emptyNode );
return true;
}
if( node -> leftNode -> nodeSize + 1 >= position )
ok = insertKey( node -> leftNode, position, key, priority );
else
ok = insertKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ), key, priority );
updateValues( node ); balanceNode( node );
return ok;
}
bool eraseKey( treapNode *&node, int position ) {
bool ok; updateValues( node );
if( node == emptyNode )
return false;
if( node -> leftNode -> nodeSize + 1 > position ) {
ok = eraseKey( node -> leftNode, position );
updateValues( node ); return ok;
}
if( node -> leftNode -> nodeSize + 1 < position ) {
ok = eraseKey( node -> rightNode, position - ( node -> leftNode -> nodeSize + 1 ) );
updateValues( node ); return ok;
}
if( node -> leftNode == emptyNode && node -> rightNode == emptyNode ) {
delete node; node = emptyNode;
return true;
}
else {
if( node -> leftNode -> priority > node -> rightNode -> priority ) {
rotateLeft( node );
ok = eraseKey( node -> rightNode, node -> rightNode -> leftNode -> nodeSize + 1 );
} else {
rotateRight( node );
ok = eraseKey( node -> leftNode, node -> leftNode -> leftNode -> nodeSize + 1 );
}
updateValues( node );
return ok;
}
}
public:
nrxPositionTreap() {
srand( time(0) );
root = emptyNode = new treapNode;
myHash.resize( MAXSIZE ); myHash[0] = make_pair( 1, 1 );
for( int i = 1; i < MAXSIZE; i ++ ) {
myHash[i].first = ( myHash[i - 1].first * CONST1 ) % MOD1;
myHash[i].second = ( myHash[i - 1].second * CONST2 ) % MOD2;
}
myHash[0] = make_pair( 0, 0 );
}
nrxPositionTreap( int SIZE ) {
srand( time(0) );
root = emptyNode = new treapNode;
myHash.resize( SIZE + 1 ); myHash[0] = make_pair( 1, 1 );
for( int i = 1; i <= SIZE; i ++ ) {
myHash[i].first = ( myHash[i - 1].first * CONST1 ) % MOD1;
myHash[i].second = ( myHash[i - 1].second * CONST2 ) % MOD2;
}
myHash[0] = make_pair( 0, 0 );
}
bool emptyTreap( void ) { return root == emptyNode; }
TYPE findMin ( void ) { return root -> minim; }
TYPE findMax ( void ) { return root -> maxim; }
TYPE findFirst( void ) { return root -> first; }
TYPE findLast ( void ) { return root -> last ; }
TYPE lowerBound( int position ) { return findKey( root, position ); }
TYPE upperBound( int position ) { return findKey( root, position ); }
TYPE rangeFirst( int left, int right ) { return findKey( root, left ); }
TYPE rangeLast ( int left, int right ) { return findKey( root, right ); }
bool insertKey( int position, TYPE key ) { return insertKey( root, position, key, rand() % INT_MAX ); }
bool eraseKey ( int position ) { return eraseKey ( root, position ); }
bool findKey ( int position ) { return findKey ( root, position ); }
int accessKey ( int position ) { return findKey( root, position ); }
void clearTreap( void ) { while( !emptyTreap() ) eraseKey( 1 ); return; }
void splitTreap( treapNode *&myTreap, int position, treapNode *&myTreap1, treapNode *&myTreap2 ) {
TYPE randomKey;
insertKey( myTreap, position + 1, randomKey, INT_MAX );
myTreap1 = myTreap -> leftNode; myTreap2 = myTreap -> rightNode;
return;
}
void joinTreap( treapNode *&myTreap1, treapNode *&myTreap2, treapNode *&myTreap ) {
TYPE randomKey; pair <int, int> randomHash;
treapNode *auxRoot = new treapNode( randomKey, 1 + myTreap1 -> nodeSize + myTreap2 -> nodeSize, INT_MIN, randomHash, myTreap1, myTreap2 );
eraseKey( auxRoot, auxRoot -> leftNode -> nodeSize + 1 ); myTreap = auxRoot;
return;
}
void rangeErase( int left, int right ) {
for( int i = left; i <= right; i ++ )
eraseKey( root, left );
return;
}
void rangeReverse( int left, int right ) {
treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4;
splitTreap( root, left - 1, myTreap1, myTreap2 );
splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );
myTreap3 -> reversed = !( myTreap3 -> reversed );
joinTreap( myTreap3, myTreap4, myTreap2 );
joinTreap( myTreap1, myTreap2, root );
return;
}
TYPE rangeMin( int left, int right ) {
treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4; TYPE minim;
splitTreap( root, left - 1, myTreap1, myTreap2 );
splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );
minim = myTreap3 -> minim;
joinTreap( myTreap3, myTreap4, myTreap2 );
joinTreap( myTreap1, myTreap2, root );
return minim;
}
TYPE rangeMax( int left, int right ) {
treapNode *myTreap1, *myTreap2, *myTreap3, *myTreap4; TYPE maxim;
splitTreap( root, left - 1, myTreap1, myTreap2 );
splitTreap( myTreap2, right - ( left - 1 ), myTreap3, myTreap4 );
maxim = myTreap3 -> maxim;
joinTreap( myTreap3, myTreap4, myTreap2 );
joinTreap( myTreap1, myTreap2, root );
return maxim;
}
};
ifstream inputFile ( "secv8.in" );
ofstream outputFile( "secv8.out" );
int N, K, X, Y; char ch;
nrxPositionTreap <int> myTreap( 250000 );
int main( int argc, const char *argv[] ){
inputFile >> N >> K;
for( int i = 1; i <= N; i ++ ) {
inputFile >> ch;
switch( ch ) {
case 'I': {
inputFile >> X >> Y;
myTreap.insertKey( X, Y );
break;
}
case 'A': {
inputFile >> X;
outputFile << myTreap.accessKey( X ) << "\n";
break;
}
case 'R': {
inputFile >> X >> Y;
myTreap.rangeReverse( X, Y );
break;
}
case 'D': {
inputFile >> X >> Y;
myTreap.rangeErase( X, Y );
break;
}
}
}
while( !myTreap.emptyTreap() ) {
outputFile << myTreap.findFirst() << " ";
myTreap.eraseKey( 1 );
}
return 0;
}