using System;
using System.Collections.Generic;
using System.Linq;



namespace CSharpSample01
{

    class Node
    {
        public int key;
        public int pri;  //priority
        public Node par;  //parent
        public Node left;
        public Node right;
        public Node(int k, int p)
        {
            key = k;
            pri = p;
            par = null;
            left = null;
            right = null;
        }
    }

    class Treap
    {
        Node root;  //根のノード
        int size;  //ノードの個数
        Node obj;
        int min;  //keyの最小値

        public Treap()
        {
            root = null;
            size = 0;
            min = 0;
        }

        public void Insert(int key, int priority)
        {
            if (size == 0) min = key;
            else min = Math.Min(min, key);

            //根がない場合、新しいノードを根とする
            if (root == null)
            {
                root = new Node(key, priority);
            }
            else
            {
                //まずは、二分木に従って挿入
                Node new_node = new Node(key, priority);
                Insert_Binary(new_node);

                //次に優先度に従って回転
                Insert_Prioriry(new_node);
            }
            size++;
        }

        //二分木に従ってnodeを挿入する
        //最終的にnodeは必ず葉として挿入される
        private void Insert_Binary(Node node)
        {
            //最初の探索対象ノードは根ノード
            Node cur = root;
            Node before = root;  //curノードの親ノードを一時的に保存

            //curにより挿入する葉の位置まで移動
            while (cur != null)
            {
                if (cur != root) before = cur.par.left == cur ? cur.par.left : cur.par.right;
                if (cur.key == node.key) return;  //keyの重複は認めない
                else if (cur.key > node.key) cur = cur.left;
                else cur = cur.right;
            }

            //nodeと親のbeforeの関係を設定
            node.par = before;

            if (node.key < before.key) before.left = node;
            else before.right = node;
            /*
            Console.WriteLine($"before:{before.key}");
            Console.WriteLine($"before.left:{(before.left != null ? before.left.key : -1)} " +
                $"before.right:{(before.right != null ? before.right.key : -1)}");
                */
        }

        //ヒープに従い、二分探索木の関係を壊さないまま回転し続ける
        //右回転または左回転を順次行う
        public void Insert_Prioriry(Node node)
        {
            Node parent = node.par;
            //Show2();
            while (true)
            {
                if (node.par == null) { root = node; break; }
                if (parent.pri > node.pri) break;
                //回転
                else if (parent.pri < node.pri)
                {                   
                    //Console.WriteLine($"node({node.key}, {node.pri}) p({parent.key}, {parent.pri})");
                    if (node == node.par.left) RightRotate(node);
                    else if (node == node.par.right) LeftRotate(node);
                    parent = node.par;
                    //Show2();
                }

            }
        }

        //右回転(nodeに関して右回転)
        private void RightRotate(Node node)
        {
            //Console.WriteLine("R");
            Node p = node.par;
            Node pp = node.par.par;
            Node r = node.right;

            //pとnode
            p.par = node;
            node.right = p;

            //rがnullの時を考慮
            if (r != null) r.par = p;
            p.left = r;

            //nodeとpp
            if (pp != null)
            {
                if (pp.left == p) pp.left = node;
                else pp.right = node;
            }
            else
            {
                //pp = nullの時、pは根だったので今度はnodeが根になる
                root = node;
            }
            node.par = pp;
        }

        //左回転(nodeに関して左回転)
        private void LeftRotate(Node node)
        {
            //Console.WriteLine("L");
            Node p = node.par;
            Node pp = node.par.par;
            Node l = node.left;

            //pとnode
            p.par = node;
            node.left = p;

            //lとp
            //lがnullの時を考慮
            if (l != null) l.par = p;
            p.right = l;

            //ppとnode
            if (pp != null)
            {
                if (pp.left == p) pp.left = node;
                else pp.right = node;
            }
            else
            {
                root = node;
            }
            node.par = pp;
        }

        //keyをもつノードを削除
        public void Erase(int key)
        {
            //Console.WriteLine("Start Erase");
            if (!Find(key)) return;         

            Node cur = obj;
            //Console.WriteLine($"Erase key:{cur.key}");
        
            while (cur.right != null || cur.left != null)
            {
                //Console.WriteLine($"cur.par key:{(cur.par != null ? cur.par.key : -1)}");
                if(cur.left != null && cur.right != null)
                {
                    if(cur.left.pri > cur.right.pri) RightRotate(cur.left);
                    else LeftRotate(cur.right);
                }
                else if (cur.left != null) RightRotate(cur.left);
                else LeftRotate(cur.right);              
            }

            if(key == min)
            {
                if (size >= 2) min = cur.par.key;
                else if (size == 1) min = 0;
            }
            
            //Console.WriteLine($"cur.par key:{(cur.par != null ? cur.par.key : -1)}");
            if (cur.par == null) root = null;
            else if (cur.par.left == cur) cur.par.left = null;
            else if (cur.par.right == cur) cur.par.right = null;
            size--;         
        }

        //keyの値を持つノードを二分木の探索方に従い再帰的に探す
        public bool Find(int key)
        {
            Node cur = root;
            obj = null;

            while (cur != null)
            {
                if (cur.key == key) { obj = cur; return true; }  //発見
                else if (cur.key > key) cur = cur.left;  //左の子へ
                else cur = cur.right;  //右の子へ
            }
            
            return false;
        }

        
        //表示
        public void Show()
        {
            if (size == 0)
            {
                Console.WriteLine("要素がありません");
                return;
            }
            Inorder(root);
            Console.WriteLine();
        }

        //表示2
        public void Show2()
        {
            if (size == 0)
            {
                Console.WriteLine("要素がありません");
                return;
            }
            Preorder(root);
            Console.WriteLine();
        }

        //中順で表示(二分探索目であるので昇順であるはず)
        public void Inorder(Node node)
        {
            if (node == null) return;

            Inorder(node.left);
            Console.Write($" {node.key}");
            Inorder(node.right);
        }

        //行きがけ順で表示
        public void Preorder(Node node)
        {
            if (node == null) return;

            Console.Write($" {node.key}");
            Preorder(node.left);
            Preorder(node.right);
        }

        //Treapのサイズを返す
        public int Size()
        {
            return size;
        }

        public void RootInfo()
        {
            if (root != null) Console.WriteLine($"key:{root.key} pri:{root.pri} " +
                 $"left:{(root.left != null ? root.left.key : -1)} " +
                 $"right:{(root.right != null ? root.right.key : -1)}");
        }

        public int GetMin()
        {
            return min;
        }
        
    }
    
    class Program
    {
        
        static void Main(string[] args)
        {
            
            int N = int.Parse(Console.ReadLine());
            Treap tp = new Treap();

            for (int i = 0; i < N; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                string order = input[0];

                int key = 0;
                int pri = 0;

                if (input.Count() == 2)
                {
                    key = int.Parse(input[1]);
                }
                if (input.Count() == 3)
                {
                    key = int.Parse(input[1]);
                    pri = int.Parse(input[2]);
                }

                if (order == "print") {tp.Show(); tp.Show2(); }
                else if (order == "size") Console.WriteLine($"size:{tp.Size()}");
                else if (order == "insert") tp.Insert(key, pri);
                else if (order == "find") Console.WriteLine(tp.Find(key) ? "yes" : "no");
                else if (order == "root") tp.RootInfo();
                else if (order == "show2") tp.Show2();
                else if (order == "delete") tp.Erase(key);
                else if (order == "end") break;
                else Console.WriteLine("no comand");
            }


        }
    }

}


Measured memory_bytes: 33892