#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _Node
{
int value;
int desc;
int reverse;
int prior;
struct _Node *left;
struct _Node *right;
} Node;
int getDesc(Node *node)
{
int desc = 1;
if (node->left)
{
desc += node->left->desc;
}
if (node->right)
{
desc += node->right->desc;
}
return desc;
}
Node *rotateLeft(Node *node)
{
Node *temp;
temp = node->left;
node->left = temp->right;
temp->right = node;
node->desc = getDesc(node);
temp->desc = getDesc(temp);
return temp;
}
Node *rotateRight(Node *node)
{
Node *temp;
temp = node->right;
node->right = temp->left;
temp->left = node;
node->desc = getDesc(node);
temp->desc = getDesc(temp);
return temp;
}
void update(Node *node)
{
Node *tmp;
if (!node || !node->reverse)
{
return;
}
if (node->left)
{
node->left->reverse ^= 1;
}
if (node->right)
{
node->right->reverse ^= 1;
}
node->reverse = 0;
tmp = node->left;
node->left = node->right;
node->right = tmp;
}
Node *balance(Node *node)
{
if (node->left && node->left->prior < node->prior)
{
return rotateLeft(node);
}
else if (node->right && node->right->prior < node->prior)
{
return rotateRight(node);
}
else
{
node->desc = getDesc(node);
return node;
}
}
Node *insert(Node *node, int key, int prior, int value)
{
if (!node)
{
node = (Node*)malloc(sizeof(Node));
node->value = value;
node->desc = 1;
node->reverse = 0;
node->prior = prior;
node->left = NULL;
node->right = NULL;
return node;
}
update(node);
update(node->left);
update(node->right);
if (key <= (node->left ? node->left->desc : 0))
{
node->left = insert(node->left, key, prior, value);
}
else
{
key -= node->left ? (node->left->desc + 1) : 1;
node->right = insert(node->right, key , prior, value);
}
return balance(node);
}
Node *erase(Node *node)
{
if (!node->left && !node->right)
{
free(node);
return NULL;
}
update(node);
update(node->left);
update(node->right);
if (node->left && node->right)
{
if (node->left->prior < node->right->prior)
{
node = rotateLeft(node);
node->right = erase(node->right);
}
else
{
node = rotateRight(node);
node->left = erase(node->left);
}
}
else if (node->left && !node->right)
{
node = rotateLeft(node);
node->right = erase(node->right);
}
else
{
node = rotateRight(node);
node->left = erase(node->left);
}
node->desc = getDesc(node);
return node;
}
int find(Node *node, int key)
{
update(node);
update(node->left);
update(node->right);
if (key == (node->left ? node->left->desc + 1 : 1))
{
return node->value;
}
if (!node->left || node->left->desc < key)
{
return find(node->right, key - (node->left ? node->left->desc + 1 : 1));
}
else
{
return find(node->left, key);
}
}
void print(Node *node, FILE *fout)
{
if (!node)
{
return;
}
update(node);
update(node->left);
update(node->right);
if (node->left)
{
print(node->left, fout);
}
fprintf(fout, "%d ", node->value);
if (node->right)
{
print(node->right, fout);
}
}
int main()
{
FILE *fin = fopen("secv8.in", "r");
FILE *fout = fopen("secv8.out", "w");
Node *root = NULL, *beg, *mdl, *end;
int i, j, k, n, e;
char buffer[100];
for (fscanf(fin, "%d %*d\n", &n); n; --n)
{
fgets(buffer, sizeof(buffer), fin);
switch (buffer[0])
{
case 'I':
{
sscanf(buffer + 1, "%d %d\n", &i, &e);
root = insert(root, i - 1, rand() + 1, e);
break;
}
case 'A':
{
sscanf(buffer + 1, "%d\n", &i);
fprintf(fout, "%d\n", find(root, i));
break;
}
case 'R':
{
sscanf(buffer + 1, "%d %d\n", &i, &j);
root = insert(root, i - 1, 0, 0);
root->right = insert(root->right, j - (i - 1), 0, 0);
beg = root->left;
mdl = root->right->left;
end = root->right->right;
mdl->reverse ^= 1;
free(root->right);
free(root);
root = (Node*)malloc(sizeof(Node));
root->left = beg;
root->right = mdl;
root->desc = getDesc(root);
root = erase(root);
beg = (Node*)malloc(sizeof(Node));
beg->left = root;
beg->right = end;
beg->desc = getDesc(beg);
root = erase(beg);
break;
}
case 'D':
{
sscanf(buffer + 1, "%d %d\n", &i, &j);
root = insert(root, i - 1, 0, 0);
root->right = insert(root->right, j - (i - 1), 0, 0);
beg = root->left;
mdl = root->right->left;
end = root->right->right;
free(root->right);
free(root);
root = (Node*)malloc(sizeof(Node));
root->left = beg;
root->right = end;
root->desc = getDesc(root);
root = erase(root);
break;
}
}
}
print(root, fout);
fclose(fin);
fclose(fout);
return 0;
}