#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <ctime>
#define infile "secv8.in"
#define outfile "secv8.out"
using namespace std;
const int inf = (int)((1LL << 31) - 1);
class Treap {
private:
struct Node {
int key, priority, size;
Node *left, *right;
bool reverse;
Node() {
reverse = false;
size = 0;
}
Node(int size, int key, int priority, Node *left, Node *right) {
this->size = size;
this->key = key;
this->priority = priority;
this->left = left;
this->right = right;
reverse = false;
}
} *root, *_empty;
void updateSize(Node* &node) {
node->size = 1 + node->left->size + node->right->size;
}
void updateReverse(Node* &node) {
if (node->reverse) {
swap(node->left, node->right);
node->reverse = false;
node->left->reverse ^= true;
node->right->reverse ^= true;
}
}
void rotLeft(Node* &node) {
Node *temp = node->left;
node->left = temp->right;
temp->right = node;
node = temp;
updateSize(node->right);
updateSize(node);
}
void rotRight(Node* &node) {
Node *temp = node->right;
node->right = temp->left;
temp->left = node;
node = temp;
updateSize(node->left);
updateSize(node);
}
void balance(Node* &node) {
if (node->left->priority > node->priority) {
updateReverse(node);
updateReverse(node->left);
rotLeft(node);
}
else if (node->right->priority > node->priority) {
updateReverse(node);
updateReverse(node->right);
rotRight(node);
}
}
void insert(Node* &node, int pos, int key, int priority) {
if (node == _empty) {
node = new Node(1, key, priority, _empty, _empty);
return;
}
updateReverse(node);
if (1 + node->left->size >= pos)
insert(node->left, pos, key, priority);
else
insert(node->right, pos - node->left->size - 1, key, priority);
updateSize(node);
balance(node);
}
int access(Node* &node, int pos) {
updateReverse(node);
if (1 + node->left->size == pos)
return node->key;
if (1 + node->left->size > pos)
return access(node->left, pos);
return access(node->right, pos - node->left->size - 1);
}
void erase(Node* &node, int pos) {
updateReverse(node);
if (1 + node->left->size > pos) {
erase(node->left, pos);
updateSize(node);
}
else if (1 + node->left->size < pos) {
erase(node->right, pos - 1 - node->left->size);
updateSize(node);
}
else {
if (node->left == _empty && node->right == _empty) {
delete node;
node = _empty;
}
else {
if (node->left->priority > node->right->priority) {
updateReverse(node->left);
rotLeft(node);
erase(node->right, node->right->left->size + 1);
updateSize(node);
}
else {
updateReverse(node->right);
rotRight(node);
erase(node->left, node->left->left->size + 1);
updateSize(node);
}
}
}
}
void split(Node* &root, int pos, Node* &root1, Node* &root2) {
insert(root, pos + 1, 0, inf);
root1 = root->left;
root2 = root->right;
delete root;
}
void join(Node* &root1, Node* &root2, Node* &root) {
Node *temp = new Node(root1->size + root2->size + 1, 0, inf, root1, root2);
erase(temp, root1->size + 1);
root = temp;
}
public:
Treap() {
root = _empty = new Node(0, 0, 0, NULL, NULL);
}
void insert(int pos, int val) {
insert(root, pos, val, rand() + 1);
}
int access(int pos) {
return access(root, pos);
}
void reverse(int pos1, int pos2) {
Node *root1, *root2, *root3, *root4;
split(root, pos1 - 1, root1, root2);
split(root2, pos2 - pos1 + 1, root3, root4);
root3->reverse ^= true;
join(root1, root3, root2);
join(root2, root4, root);
}
void erase(int pos1, int pos2) {
for (int index = pos1; index <= pos2; ++index)
erase(root, pos1);
}
void print(ofstream &fout) {
for (int index = 1; index <= root->size; ++index)
fout << access(index) << ' ';
fout << '\n';
}
} treap;
int main() {
ifstream fin(infile);
ofstream fout(outfile);
srand(time(NULL));
int opCount;
char op;
fin >> opCount >> op;
for (int index = 1; index <= opCount; ++index) {
fin >> op;
if (op == 'I') {
int pos, val;
fin >> pos >> val;
treap.insert(pos, val);
}
else if (op == 'A') {
int pos;
fin >> pos;
fout << treap.access(pos) << '\n';
}
else if (op == 'R') {
int pos1, pos2;
fin >> pos1 >> pos2;
treap.reverse(pos1, pos2);
}
else if (op == 'D') {
int pos1, pos2;
fin >> pos1 >> pos2;
treap.erase(pos1, pos2);
}
}
treap.print(fout);
return 0;
}
//Trust me, I'm the Doctor!
Iordache Ioan-Bogdan iordache.bogdan