#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;
}