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

namespace _20190108_AOJ
{
    class ALDS1_8D
    {
        static void Main(string[] args)
        {
            for (;;)
            {
                string line = Console.ReadLine();
                if (string.IsNullOrEmpty(line))
                {
                    break;
                }

                Treap bt = new Treap();
                int n = int.Parse(line);
                for (int i = 0; i < n; i++)
                {
                    string[] command = Console.ReadLine().Split(' ');
                    int key;
                    int priority;
                    switch (command[0])
                    {
                        case "delete":
                            key = int.Parse(command[1]);
                            bt.Delete(key);
                            break;
                        case "find":
                            key = int.Parse(command[1]);
                            TreeNode tn = bt.Find(key);
                            if (tn != null)
                            {
                                Console.WriteLine("yes");
                            }
                            else
                            {
                                Console.WriteLine("no");
                            }
                            break;
                        case "insert":
                            key = int.Parse(command[1]);
                            priority = int.Parse(command[2]);
                            bt.Insert(key, priority);
                            break;
                        case "print":
                            Console.Write(" ");
                            Console.WriteLine(string.Join(" ", bt.InOrder().Select(x => x.Key.ToString()).ToArray()));
                            Console.Write(" ");
                            Console.WriteLine(string.Join(" ", bt.PreOrder().Select(x => x.Key.ToString()).ToArray()));
                            break;
                    }
                }
            }
        }
    }

    class Treap
    {
        List<TreeNode> list;
        public TreeNode Root { get { return GetRoot(); } }
        public Treap()
        {
            list = new List<TreeNode>();
        }

        private TreeNode GetRoot()
        {
            if (list.Count == 0) return null;

            TreeNode temp = list[0];
            while (temp.Parent != null)
            {
                temp = temp.Parent;
            }

            return temp;
        }

        public TreeNode RightRotate(TreeNode t)
        {
            TreeNode s = t.Left;
            t.Left = s.Right;
            s.Right = t;
            s.Parent = t.Parent;
            t.Parent = s;

            return s;   // root of the subtree
        }

        public TreeNode LeftRotate(TreeNode t)
        {
            TreeNode s = t.Right;
            t.Right = s.Left;
            s.Left = t;
            s.Parent = t.Parent;
            t.Parent = s;

            return s;   // root of the subtree
        }

        public TreeNode Insert(int key, int priority)
        {
            return Insert(Root, key, priority);
        }

        public TreeNode Insert(TreeNode t, int key, int priority)
        {
            if (t == null)
            {
                TreeNode tn = new TreeNode(key, priority);
                list.Add(tn);
                return tn;
            }

            if (key == t.Key)
            {
                return t;
            }

            if (key < t.Key)
            {
                t.Left = Insert(t.Left, key, priority);
                t.Left.Parent = t;
                if (t.Priority < t.Left.Priority)
                {
                    t = RightRotate(t);
                }
            }
            else
            {
                t.Right = Insert(t.Right, key, priority);
                t.Right.Parent = t;
                if (t.Priority < t.Right.Priority)
                {
                    t = LeftRotate(t);
                }
            }

            return t;
        }

        public TreeNode Delete(int key)
        {
            return Delete(Root, key);
        }

        public TreeNode Delete(TreeNode t, int key)
        {
            if (t == null)
            {
                return null;
            }

            if (key < t.Key)
            {
                t.Left = Delete(t.Left, key);
            }
            else if (key > t.Key)
            {
                t.Right = Delete(t.Right, key);
            }
            else
            {
                return _Delete(t, key);
            }

            return t;
        }

        private TreeNode _Delete(TreeNode t, int key)
        {
            if(t.Left == null && t.Right == null)
            {
                list.Remove(t);
                return null;
            }
            else if(t.Left == null)
            {
                t = LeftRotate(t);
            }
            else if(t.Right == null)
            {
                t = RightRotate(t);
            }
            else
            {
                if (t.Left.Priority > t.Right.Priority)
                {
                    t = RightRotate(t);
                }
                else
                {
                    t = LeftRotate(t);
                }
            }

            return Delete(t, key);
        }

        public TreeNode Find(int key)
        {
            return Find(Root, key);
        }

        static TreeNode Find(TreeNode tn, int key)
        {
            TreeNode rv = null;
            if (tn != null)
            {
                if (key < tn.Key)
                {
                    rv = Find(tn.Left, key);
                }
                else if (key > tn.Key)
                {
                    rv = Find(tn.Right, key);
                }
                else
                {
                    rv = tn;
                }
            }

            return rv;
        }

        public TreeNode[] PreOrder()
        {
            List<TreeNode> list = new List<TreeNode>();
            PreOrder(list, Root);
            return list.ToArray();
        }

        static void PreOrder(List<TreeNode> list, TreeNode tn)
        {
            list.Add(tn);

            if (tn.Left != null)
            {
                PreOrder(list, tn.Left);
            }

            if (tn.Right != null)
            {
                PreOrder(list, tn.Right);
            }
        }

        public TreeNode[] InOrder()
        {
            List<TreeNode> list = new List<TreeNode>();
            InOrder(list, Root);
            return list.ToArray();
        }

        static void InOrder(List<TreeNode> list, TreeNode tn)
        {
            if (tn.Left != null)
            {
                InOrder(list, tn.Left);
            }

            list.Add(tn);

            if (tn.Right != null)
            {
                InOrder(list, tn.Right);
            }
        }

        static void PostOrder(List<TreeNode> list, TreeNode tn)
        {
            if (tn.Left != null)
            {
                PostOrder(list, tn.Left);
            }

            if (tn.Right != null)
            {
                PostOrder(list, tn.Right);
            }

            list.Add(tn);
        }
    }

    class TreeNode
    {
        public int Key { get; set; }
        public int Priority { get; set; }
        public TreeNode Parent { get; set; }
        public TreeNode Left { get; set; }
        public TreeNode Right { get; set; }
        public TreeNode()
        {
        }

        public TreeNode(int key, int priority)
        {
            this.Key = key;
            this.Priority = priority;
        }
    }
}


Measured memory_bytes: 66148