#include <fstream>
#include <ctime>
#include <cstdlib>
using namespace std;

ifstream F("schi.in");
ofstream G("schi.out");

const int infi = 1<<30;

struct treap
{
    int key,priority;
    treap *left,*right;
    treap() {}
    treap(int key,int priority,treap *left,treap *right)
    {
        this->key = key;
        this->priority = priority;
        this->left = left;
        this->right = right;
    }
} *tree, *_null;

void init(treap* &tree)
{
    srand(unsigned(time(0)));
    tree = _null = new treap(0,0,NULL,NULL);
}

int search(treap* t,int key)
{
    if ( t == _null ) return 0;
    if ( key == t->key ) return 1;
    if ( key < t->key )
        return search(t->left,key);
    else
        return search(t->right,key);
}

void rleft(treap *&z) // st -> dr
{
    treap *w = z->left;
    z->left = w->right;
    w->right = z;
    z = w;
}

void rright(treap *&w) // dr -> st
{
    treap *z = w->right;
    w->right = z->left;
    z->left = w;
    w = z;
}

void balance(treap *&t)
{
    if ( t->left->priority > t->priority )
        rleft(t);
    else
        if ( t->right->priority > t->priority )
            rright(t);
}

void insert(treap *&n,int key,int priority)
{
    if ( n == _null )
    {
        n = new treap(key,priority,_null,_null);
        return;
    }
    if ( key < n->key )
        insert(n->left,key,priority);
    else
        if ( key > n->key )
            insert(n->right,key,priority);
    balance(n);
}

void erase(treap *&n,int key)
{
    if ( n == _null ) return;
    if ( key < n->key )
        erase(n->left,key);
    else
        if ( key > n->key )
            erase(n->right,key);
        else
        {
            if ( n->left == _null && n->right == _null )
            {
                delete n;
                n = _null;
            }
            else
            {
                if ( n->left->priority > n->right->priority )
                    rleft(n);
                else
                    rright(n);
                erase(n,key);
            }
        }
}

void split(treap *&n,treap *&l,treap *&r,int key)
{
    insert(n,key,infi);
    l = n->left;
    r = n->right;
    delete n;
    n = _null;
}

void join(treap *&n,treap *l,treap *r,int key)
{
    n = new treap(key,-infi,l,r);
    erase(n,n->key);
}

int main()
{
}