#include <iostream>
#include <assert.h>
#include <ctype.h>

using namespace std;

// The structure we will use to build our Splay Tree (which is a
// binary search tree that inserts and removes in strange ways.)
struct SplayNode
{
  int val;
  SplayNode* left;
  SplayNode* right;
};

// Predeclarations
SplayNode* Splay(int val, SplayNode* cur);
void print(SplayNode* root, int d);

// To make FindMin and FindMax easy
const int NegInfinity = -1000000000;
const int    Infinity =  1000000000;

// Find is simply a matter of calling Splay, which ensures
// that the node closest to the value you chose comes to the top
SplayNode* Find(int toFind, SplayNode* root)
{
  return Splay(toFind, root);
}

// Find the node with the smallest value
SplayNode* FindMin(SplayNode* root)
{
  return Splay(NegInfinity, root);
}

// Find the node with the largest value
SplayNode* FindMax(SplayNode* root)
{
  return Splay(Infinity, root);
}

// Given the tree:
//    r
//   / \
//  c   []
// /\
//[] []
// Return the tree:
//    c
//   / \
//  []  r
//      /\
//     [] []
SplayNode* SingleRotateWithLeft(SplayNode* root)
{
  SplayNode* newRoot = root->left;
  root->left = newRoot->right;
  newRoot->right = root;
  return newRoot;
}

// Given the tree:
//    r
//   / \
//  []  c
//      /\
//     [] []
// Return the tree:
//    c
//   / \
//  r   []
// /\
//[] []
SplayNode* SingleRotateWithRight(SplayNode* root)
{
  SplayNode* newRoot = root->right;
  root->right = newRoot->left;
  newRoot->left = root;
  return newRoot;
}

// Now THIS is the weird bit.
// This ensures that the node closest to val will be brought to the
// top, but the binary search tree properties will be upheld at
// every step. 
 
// FURTHERMORE, if we are forced to perform n operations, then
// each of those operations is a double-rotation, which will
// wind up cutting the height of the tree in half.  After that
// there is no series of operations shorter than n that will allow
// an n-step operation.  When a SplayTree detects that it is
// being stored inefficiently, the resulting expensive operation
// has a side-effect of greatly reducing the height of the tree

// And better STILL, you can prove that if keys i are searched for
// with probability f(i), then the time to find key i is O(n log
// (n/f(i))) Meaning that if a key is searched a constant fraction of
// the time (rather than an inverse-function of n), then it will be
// found in O(1).

// This is what we call a top-down Splay, which implements the same
// operations as the zig, zig-zag, zig-zig operations discussed in
// lecture, but does so much quicker and with less code.
SplayNode* Splay(int val, SplayNode* cur)
{
  // We hold a single on-stack temp
  SplayNode temp;

  // This holds, if filled in, the left child of the right subtree
  SplayNode* RightTreeMin;
  
  // This holds, if filled in, the right child of the left subtree
  SplayNode* LeftTreeMax;

  // Temp initially doesn't go anywhere
  temp.left = NULL;
  temp.right = NULL;

  // But Right and Left _start out_ (but do not remain, this is important)
  // as aliases for temp.
  RightTreeMin = &temp;
  LeftTreeMax = &temp;
  
  // Now, while we haven't gotten to the node that we want
  while (cur->val != val)
    {
      // Go left
      if (cur->val > val)
	{
	  // If we could go left twice, then it is healthier
	  // (and will balance more) to rotate once.
	  if (cur->left and cur->left->val > val)
	    {
	      // This has the effect of bringing cur down one level
	      // (well, it is still the same level, but now there are
	      // other things distributed around.  Draw it out 
	      // to see what I mean.)
	      cur = SingleRotateWithLeft(cur);
	    }
	  // If we are falling off the end, time to stop
	  if (cur->left == NULL) break;

	  // A weird bit: Remember that the small side of whatever
	  // Right is should now point to cur (we're swapping cur
	  // down and cur->left up)
	  RightTreeMin->left = cur;

	  // Now update Right to point to cur
	  RightTreeMin = cur;

	  // And update cur so we're down one more level
	  cur = cur->left;
	}
      else
	{
	  // If we could go right twice, then just rotate once
	  if (cur->right and cur->right->val < val)
	    {
	      cur = SingleRotateWithRight(cur);
	    }
	  // If we are falling off, stop
	  if (cur->right == NULL) break;

	  // This is basically swapping cur down one and 
	  // cur->right up one, but won't be "finished" until
	  // the loop is done.  That's really why this code 
	  // is so kooky.
	  LeftTreeMax->right = cur;
	  LeftTreeMax = cur;
	  cur = cur->right;
	}
    }

  // Now, the left tree (which is somewhere near the bottom of our return
  // tree) should have what was left of the new root as it's right child.
  // (We are moving whole subtrees here, but have to maintain order)
  LeftTreeMax->right = cur->left;

  // And the opposite of the above
  RightTreeMin->left = cur->right;

  // Temp is holding bits of our tree, but since temp
  // was originally Right and Left, it's all bass-ackwards.  We fill
  // in our return values here.
  cur->left = temp.right;
  cur->right = temp.left;

  // And we are done
  return cur;
}

// After that Splay stuff, which I admit is mostly magic,
// Insert is way easy.
SplayNode* Insert(int val, SplayNode* cur)
{
  // Basic tree insertion stuff.  If inserting in an 
  // empty tree, return the new node.
  SplayNode* newNode = new SplayNode;
  newNode->val = val;
  if (cur == NULL)
    {
      newNode->left = NULL;
      newNode->right = NULL;
      return newNode;
    }
  
  // Now, Splay the value we want up to the top.
  cur = Splay(val, cur);

  // If the closest we can get is too large, then make it 
  // our right subtree
  if (val < cur->val)
    {
      newNode->left = cur->left;
      newNode->right = cur;
      cur->left = NULL;
      cur = newNode;
    }
  // If our closest was too small, then make it our left subtree
  else if (val > cur->val)
    {
      newNode->right = cur->right;
      newNode->left = cur;
      cur->right = NULL;
      cur = newNode;  
    }
    
  // All done
  return cur;
}

// Much like Insert, Remove is now very easy with Splay
SplayNode* Remove(int val, SplayNode* cur)
{
  // Basic removal stuff
  SplayNode* temp;
  if (cur == NULL) return cur;

  // Splay the target node up to the top
  cur = Splay(val, cur);
 
  // If we found it
  if (val == cur->val)
    {
      // If we can just promote a child, do so
      if (cur->left == NULL) 
	temp = cur->right;
      else if (cur->right == NULL)
	temp = cur->left;
      // Otherwise, do something odd:
      else
	{
	  // Splay up the same value.  Since we
	  // only can have one of the same values in the tree
	  // at once, this is gonna find us the closest thing in the 
	  // left tree.
	  temp = cur->left;
	  temp = Splay(val, temp);

	  // Now do the same tweaking as above
	  temp->right = cur->right;
	}
      // Delete cur
      delete cur;

      // Update
      cur = temp;
    }
  
  // Done
  return cur;
}

// Simple print function
void print(SplayNode* root, int d)
{
  // Base case
  if (root == NULL) return;

  // Print left 
  print(root->left, d + 1);

  // Print root
  for (int i = 0; i < d; i++)
    cout << "  ";
  cout << root->val << endl;

  // Print right
  print(root->right, d + 1);
}

int main()
{
  SplayNode* root = NULL;
  char op;
  int num;
  while (cin >> op >> num)
    {
      op = tolower(op);
      if (op == 'i') root = Insert(num, root);
      if (op == 'r') root = Remove(num, root);
      if (op == 's') root = Splay(num, root);
      print(root, 0);
      cout << endl;
    }
}