#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 9;

class Treapuri{
    public:
    struct treap{
        treap* st;
        treap* dr;
        int val;
        int g;
        treap(treap* stanga, treap*dreapta, int v, int gr){
            this -> st = stanga;
            this -> dr = dreapta;
            this -> val = v;
            this -> g = gr;
        }
        treap(){
            this -> st = NULL;
            this -> dr = NULL;
            this -> val = -1;
            this -> g = 0;
        }
    };
    treap *NILL, *root;
    int random(){
        return (rand()<<15 + rand())%MOD + 1;
    }
    void Start(){
        NILL = new treap();
        root = NILL;
    }

    void leftRotate(treap*& node){
        treap* aux;
        aux = node->st;
        node->st = aux->dr;
        aux->dr = node;
        node = aux;
    }

    void rightRotate(treap*& node){
        treap* aux;
        aux = node->dr;
        node->dr = aux->st;
        aux->st = node;
        node = aux;
    }

    void balance(treap*& node){
        if(node->st != NILL && node->st->g > node-> g) leftRotate(node);
        if(node->dr != NILL && node->dr->g > node-> g) rightRotate(node);
    }

    void Add(treap *& node, int valoare){
        if(node == NILL){
            node = new treap(NILL, NILL, valoare, random());
            return;
        }
        if(node->val > valoare) Add(node->st, valoare);
        else Add(node->dr, valoare);
        balance(node);
    }

    bool findd(treap*& node, int valoare){
        if(node == NILL) return 0;
        if(node->val == valoare) return 1;
        if(node->val > valoare) return findd(node->st, valoare);
        else return findd(node->dr, valoare);
    }

    void erasee(treap*& node, int valoare){
        if(node == NILL) return;

        if(node->val == valoare){
            if(node->st == NILL && node->dr == NILL){
                delete(node);
                node = NILL;
                return;
            }
            if(node->st != NILL && node->dr != NILL){
                if(node->st->g > node->dr->g){
                    leftRotate(node);
                    erasee(node->dr, valoare);
                    return;
                }
                rightRotate(node);
                erasee(node->st, valoare);
                return;
            }

            if(node->st != NILL){
                leftRotate(node);
                erasee(node->dr, valoare);
                return;
            }
            rightRotate(node);
            erasee(node->st, valoare);
            return;
        }
        if(node->val > valoare) erasee(node->st, valoare);
        else erasee(node->dr, valoare);
    }

}*Treapulet;

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

int main(){
    int n;
    f >> n;
    Treapulet = new Treapuri;
    Treapulet->Start();
    for(int i = 0; i < n; ++ i){
        int cd, temp;
        f >> cd >> temp;
        if(cd == 1 && !Treapulet->findd(Treapulet->root, temp)) Treapulet->Add(Treapulet->root, temp);
        if(cd == 2 && Treapulet->findd(Treapulet->root, temp)) Treapulet->erasee(Treapulet->root, temp);
        if(cd == 3) g << Treapulet->findd(Treapulet->root, temp) << '\n';
    }
    return 0;
}