using System;
using System.IO;
using System.Linq;

namespace Binary_search_trees
{
    class Program
    {

        class Treap
        {
            public class Node
            {
                internal int val;
                internal int priority;
                internal Node left, right;
                internal Node parent;

                internal Node(int val, int priority)
                {
                    this.val = val;
                    this.priority = priority;
                    left = right = parent = null;
                }
            }

            Node root;

            public Treap()
            {
                root = null;
            }

            internal Node RightRotate(Node t)
            {
                Node s = t.left;
                s.parent = t.parent;
                if (t.parent == null)
                    root = s;

                t.left = s.right;
                if (s.right != null) s.right.parent = t;

                s.right = t;
                t.parent = s;

                return s;
            }
            internal Node LeftRotate(Node t)
            {
                Node s = t.right;
                s.parent = t.parent;
                if (t.parent == null)
                    root = s;

                t.right = s.left;
                if (s.left != null) s.left.parent = t;

                s.left = t;
                t.parent = s;

                return s;
            }

            public Node Insert(Node t, int key, int priority)
            {
                if (t == null)
                    return new Node(key, priority);

                if (key == t.val)
                    return t;

                if (key < t.val)
                {
                    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 void Insert(int key, int priority)
            {
                if (root == null) root = new Node(key, priority);
                else Insert(root, key, priority);
            }

            public void Erase(int key)
            {
                Delete(root, key);
            }

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

                if (key < t.val)
                    t.left = Delete(t.left, key);
                else if (key > t.val)
                    t.right = Delete(t.right, key);
                else
                    return _Delete(t, key);

                return t;
            }

            private Node _Delete(Node t, int key)
            {
                if (t.left == null && t.right == null)
                    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 Node Find(int elem)
            {
                Node n = root;
                while (n != null)
                {
                    if (n.val > elem) n = n.left;
                    else if (n.val < elem) n = n.right;
                    else break;
                }
                return n;
            }

            public bool Contains(int elem)
            {
                return Find(elem) != null;
            }

            public void PrintPreorder(Node n)
            {
                if (n == null) return;
                Console.Write(" " + n.val);
                PrintPreorder(n.left);
                PrintPreorder(n.right);
            }

            public void PrintPreorder()
            {
                PrintPreorder(root);
                Console.WriteLine();
            }

            public void PrintInorder(Node n)
            {
                if (n == null) return;
                PrintInorder(n.left);
                Console.Write(" " + n.val);
                PrintInorder(n.right);
            }

            public void PrintInorder()
            {
                PrintInorder(root);
                Console.WriteLine();
            }
        }

        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var treap = new Treap();
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            for (int i = 0; i < n; i++)
            {
                var line = Console.ReadLine();
                switch (line[0])
                {
                    case 'i':
                        var kp = line.Substring(7).Split(' ').Select(s => int.Parse(s)).ToArray();
                        treap.Insert(kp[0], kp[1]);
                        break;
                    case 'f':
                        if (treap.Contains(int.Parse(line.Substring(5)))) Console.WriteLine("yes");
                        else Console.WriteLine("no");
                        break;
                    case 'd':
                        treap.Erase(int.Parse(line.Substring(7)));
                        break;
                    case 'p':
                        treap.PrintInorder();
                        treap.PrintPreorder();
                        break;
                }
            }
            Console.Out.Flush();
        }

    }
}



Measured memory_bytes: 30300