// \begin{verbatim}
    #include<iostream>
    #include<cstdio>
    #include<iomanip>
    #include<cassert>
    #include<string>
    #include<cmath>
    #include<iostream>
    #include<cmath>
    #include<sstream>
    #include<stdio.h>
    #include<stdlib.h>
     using namespace std;

  const int N = 20;
  const int base = 64;
  const int alphsize = 26;

  const int randomcap = 100;
  const int rndoffset = 10;

  int randm()
   {
    // random 2 digit number
    return rndoffset+rand()%(randomcap-rndoffset);
   }

  struct treapnode;
  typedef treapnode*treap;
  struct treapnode
   {
    char kye;  
    int prty;
    treap lft = NULL;
    treap rght = NULL;
   };

  bool heaporder(treap t,int mx)
   {
    if(!t) return true;
    else if(t->prty > mx) return false;
    else return heaporder(t->lft,t->prty) and heaporder(t->rght,t->prty);
   }

  int nmbr(treap t)
   {
    if(t)
     return 1 + nmbr(t->lft)+nmbr(t->rght);
    else return 0;
   }

  int hite(treap t)
   {
    if(t)
     return 1 + max(hite(t->lft),hite(t->rght));
    else return -1;
   }

  void lftrotate(treap&t)
   {
    assert(t);
    treap tmp = t->rght;
    assert(tmp);
    //assert(t->prty <= tmp->prty);
    t->rght = tmp->lft;
    tmp->lft = t;
    t = tmp;
   }

  void rghtrotate(treap&t)
   {
    assert(t);
    treap tmp = t->lft;
    assert(tmp);
    //assert(t->prty <= tmp->prty);
    t->lft = tmp->rght;
    tmp->rght = t;
    t = tmp;
   }

  void stoor(treap&t,char v)
   {
    // insert
    if(!(t))
     {
      t = new treapnode;
      t->kye = v;
      t->prty = randm();
     }
    else if(v < t->kye)
     {
      stoor(t->lft,v);
      if(t->prty < t->lft->prty)
       rghtrotate(t);
     }
    else
     {
      stoor(t->rght,v);
      if(t->prty < t->rght->prty)
       lftrotate(t);
     }
   }

  void preorder(treap t)
   {
    //if(!t) cout << "t is empty!" << endl;
    //cout << t->kye << endl;
    if(t)
     {
      cout << t->kye << t->prty << " ";
      preorder(t->lft);
      preorder(t->rght);
     }
   }

  void inorder(treap t)
   {
    if(t)
     {
      inorder(t->lft);
      cout << t->kye << t->prty << " ";
      inorder(t->rght);
     }
   }

  void postorder(treap t)
   {
    if(t)
     {
      postorder(t->lft);
      postorder(t->rght);
      cout << t->kye << t->prty << " ";
     }
   }

  treap mainroot = NULL;

  void storechars()
   {
    char v;
    for(int i = 0; i < N; i++)
     {
      cin >> v;
      //cout << v << " ";
      stoor(mainroot,v);
     }
   }

  void dlete(treap&t)
   {
    if(t)
     if(t->rght)
      if(t->lft)
       if(t->lft->prty < t->rght->prty)
        {
         lftrotate(t);
         dlete(t->lft);
        }
       else
        {
         rghtrotate(t);
         dlete(t->rght);
        }
      else t = t->rght;
     else t = t->lft;
   }

  void dlete(treap&t,char dlt)
   {
    if(t)
     if(t->kye == dlt) dlete(t);
     else if(t->kye < dlt) dlete(t->rght,dlt);
     else  dlete(t->lft,dlt);
    else cout << "  Not found";
   }

  void sketsh(treap t,int dpth)
   {
    // Tilt your head to the left to view the treap.
    if(t)
     {
      sketsh(t->rght,dpth+1);
      for(int d = 0; d < dpth; d++) cout << " ";
      cout << t->kye << t->prty << endl;
      sketsh(t->lft,dpth+1);
     }
   }

  bool iskey(treap t,char fnd)
   {
    if(t)
     if(t->kye == fnd) return true;
     else if(fnd < t->kye) return iskey(t->lft,fnd);
     else return iskey(t->rght,fnd);
    else return false;
   }

  treap findptr(treap t,char fnd)
   {
    if(t)
     if(t->kye == fnd) return t;
     else if(fnd < t->kye) return findptr(t->lft,fnd);
     else return findptr(t->rght,fnd);
    else return NULL;
   }

  void findall(treap root)
   {
    for(int i = 1; i <= alphsize; i++)
     {
      char fnd = char(base+i);
      cout << fnd;
      if(iskey(root,fnd)) cout << " Found" << endl;
      else cout << " Not found" << endl;
     }
   }

  void dsplay(treap t)
   {
    cout << "preorder:" << endl;
    preorder(t);
    cout << endl;
    cout << "inorder:" << endl;
    inorder(t);
    cout << endl;
    cout << "postorder:" << endl;
    postorder(t);
    cout << endl;
    cout << "The tree has " << nmbr(t) << " nodes and height "
         << hite(t) << endl;
    sketsh(t,0);
   }

  int main()
   {
    srand(2);
    storechars();
    int n;
    cin >> n;
    dsplay(mainroot);
    cout << "DeLete " << 'M' << ":  ";
    dlete(mainroot,'M');
    if(not heaporder(mainroot,randomcap))
          cout << "data not in heap order" << endl;
    cout << endl;
    dsplay(mainroot);
    cout << "Delete " << 'M' << ":  ";
    dlete(mainroot,'M');
    if(not heaporder(mainroot,randomcap))
          cout << "data not in heap order" << endl;
    cout << endl;
    //findall(mainroot);
    return 1;
   }
// \end{verbatim}