#include <cstdio>

using namespace std;

class Treap{
public:
    int priority;
    int value;
    Treap *st,*dr;
    Treap(){
        priority = value = 0;
        st = dr = 0;
    }
    Treap(int value,int priority,Treap *st, Treap *dr){
        this->value = value;
        this->priority = priority;
        this->st = st;
        this->dr = dr;
    }
};
Treap *root,*nil;

void Rotate_left(Treap *&T)
{
    Treap *aux = T->st;
    T->st = aux->dr;
    aux->dr = T;
    T = aux;
}
void Rotate_right(Treap *&T)
{
    Treap *aux = T->dr;
    T->dr = aux->st;
    aux->st = T;
    T = aux;
}
void Balance(Treap *&T)
{
    if(T->st->priority > T->priority)
        Rotate_left(T);
    else
        if(T->dr->priority > T->priority)
            Rotate_right(T);
}
void Insert(int value,int priority,Treap *&T)
{
    if(T == nil){
        T = new Treap(value,priority,nil,nil);
        return;
    }
    if(T->value> value)
        Insert(value,priority,T->st);
    else
        Insert(value,priority,T->dr);
    Balance(T);
}

void parcurgere(Treap *T)
{
    if(T == nil)return;
    parcurgere(T->st);
    printf("%d ",T->value);
    parcurgere(T->dr);
}
int Search(int value,Treap *T)
{
    if(T == nil) return 0;
    if(T->value == value) return 1;
    if(T->value > value)
        return Search(value, T->st);
    return Search(value, T->dr);
}
void Delete(int value,Treap *&T)
{
    if(T == nil) return;
    if(T->value > value)
        Delete(value,T->st);
    else
        if(T->value < value)
            Delete(value,T->dr);
        else
            if(T->st == nil && T->dr == nil){ delete T; T = nil; return;}
            else
            {
                if(T->st->priority > T->dr->priority)   Rotate_left(T);
                else    Rotate_right(T);
                Delete(value,T);
            }
}
Treap *Tmic,*Tmare;

void Split(int value,Treap *&T)
{
    Insert(value,0x3f3f3f3f,T);
    Tmic = T->st;
    Tmare = T->dr;
    Delete(value,T);
}

int main()
{
    freopen("treapuri.in","r",stdin);
    ///freopen("treapuri.out","w",stdout);

    root = nil = new Treap(0,0,0,0);
    Insert(14,23,root);
    Insert(12,50,root);
    Insert(24,39,root);
    Insert(19,77,root);

    Split(17,root);

    parcurgere(Tmic);
    printf("\n");
    parcurgere(Tmare);

    return 0;
}