#include <fstream>
#include <cstdlib>
#include <ctime>
#include <map>

using namespace std;

ifstream f("treapuri.in");
ofstream g("treapuri.out");

map<int, int> MyMap;

struct TreapNode
{
    int Key, Priority;
    TreapNode *LeftSon;
    TreapNode *RightSon;

    TreapNode () {}

    TreapNode (int Key, int Priority, TreapNode* Left, TreapNode *Right)
    {
        this->Key=Key;
        this->Priority=Priority;
        this->LeftSon=Left;
        this->RightSon=Right;
    }
} *Root, *Null;

void Initialize (TreapNode* &Root)
{
    srand(time(0));
    Root=Null=new TreapNode(0, 0, 0, 0);
}

int Search (TreapNode* Node, int value)
{
    if (Node==Null) return 0;
    if (Node->Key==value) return Node->Priority;

    if (value<Node->Key)
        return Search(Node->LeftSon, value);

    return Search(Node->RightSon, value);
}

void RotateLeft (TreapNode* &Node)
{
    TreapNode *Aux=Node;

    Aux->LeftSon=Node->LeftSon->RightSon;
    Node=Node->LeftSon;
    Node->RightSon=Aux;
}

void RotateRight (TreapNode* &Node)
{
    TreapNode *Aux=Node;

    Aux->RightSon=Node->RightSon->LeftSon;
    Node=Node->RightSon;
    Node->LeftSon=Aux;
}

void Balance (TreapNode* &Node)
{
    if (Node->Priority < Node->LeftSon->Priority)
    {
        RotateLeft(Node);
        return;
    }
    if (Node->Priority < Node->RightSon->Priority)
    {
        RotateRight(Node);
        return;
    }
}

void Insert (TreapNode* &Node, int value, int priority)
{
    if (Node==Null)
    {
        Node=new TreapNode(value, priority, Null, Null);
        return;
    }

    if (value==Node->Key) return;

    if (value<Node->Key)
        Insert(Node->LeftSon, value, priority);
    else
        Insert(Node->RightSon, value, priority);

    Balance(Node);
}

void Erase (TreapNode* &Node, int value)
{
    if (Node==Null) return;

    if (value==Node->Key)
    {
        if (Node->LeftSon==Null && Node->RightSon==Null)
        {
            delete Node;
            Node=Null;
        }
        else
        {
            if (Node->LeftSon->Priority > Node->RightSon->Priority)
                RotateLeft(Node);
            else
                RotateRight(Node);
            Erase(Node, value);
        }
        return;
    }

    if (value<Node->Key)
        Erase(Node->LeftSon, value);
    else
        Erase(Node->RightSon, value);
}

void Split (TreapNode* &Root, TreapNode* &LeftTreap, TreapNode* &RightTreap, int value)
{
    Insert(Root, value, 0x3f3f3f3f);
    LeftTreap=Root->LeftSon;
    RightTreap=Root->RightSon;

    delete Root;
    Root=Null;
}

void Join (TreapNode* &Root, TreapNode* &LeftTreap, TreapNode* &RightTreap, int value)
{
    Root=new TreapNode(value, 0, LeftTreap, RightTreap);
    Erase(Root, Root->Key);
}

void Push (int value)
{
    int newpriority=rand()%(999999999)+1;
    Insert(Root, value, newpriority);
    MyMap[value]=newpriority;
}

void CheckSearch (int value)
{
    if (MyMap[value]!=Search(Root, value))
        g << value << ' ' << MyMap[value] << ' ' << Search(Root, value) << ' ' << "Error! WA!\n";
    else
        g << "OK!\n";
}

int main ()
{
    Initialize(Root);

    int T;
    for (f >> T; T>=1; T--)
    {
        int o, v;
        f >> o >> v;

        if (o==1)
            Push(v);
        if (o==2)
        {
            MyMap[v]=0;
            Erase(Root, v);
        }
        if (o==3)
            CheckSearch(v);
    }

    f.close();
    g.close();

    return 0;
}