# include <bits/stdc++.h>

using namespace std;

struct node {
    int key;
    int height;
    node * left, *right, *parent;

      node() { left = right = parent = NULL; }
    node(int Key,node * par) { key = Key; left = right = parent = NULL; parent = par; }
};

node * root = NULL;

int get_height(node *A) {
    return A == NULL ? 0 : max(get_height(A->left),get_height(A->right)) + 1;
}
void RotateLeft(node *& B);
void RotateRight(node *& A)
{
    node * par = A->parent;
    node * B = A->left;

        int hl = get_height(B->left);
        int hr = get_height(B->right);

        if (hr > hl) RotateLeft(B);
    B = A->left;

  if (par!=NULL)  if (par->left == A) par->left = B; else par->right = B; else root = B;
  B->parent = A->parent;
  A->parent = B;
    A->left = B->right; if (B->right) B->right->parent = A;
    B->right = A;
}

void RotateLeft(node *& B)
{
    node * par = B->parent;
    node * A = B->right;

        int hl = get_height(A->left);
        int hr = get_height(A->right);

        if (hl > hr) RotateRight(A);
   A = B->right;

  if (par!=NULL)  if (par->left == B) par->left = A;else par->right = A; else root = A;
  A->parent = par;
  B->parent = A;
    B->right = A->left; if (A->left) A->left->parent = B;
    A->left = B;
}

void GetBalance(node * &curent)
{
    while (curent != NULL) {
        int hleft = get_height(curent->left);
        int hright = get_height(curent->right);
        //cout << curent->key << " " << hleft << " " << hright << " hh " << endl;

                 node * tmp = curent;

            if (hleft - hright > 1) RotateRight(curent);
            else if (hleft - hright < -1) RotateLeft(curent);

        curent = tmp->parent;
    }
}

node * inAVL(int key)
{
     node * curent = root;
     while(curent != NULL) {
        if (curent->key == key) return  curent;
        else if (key < curent->key) curent = curent->left;
        else curent = curent->right;
     }
     return curent;
}


void Insereaza(int key)
{

    if (inAVL(key)) return;

    if (root == NULL) {
        root = new node(key,NULL);
        return;
    }
    node * curent = root;
    while (curent != NULL) {
        if (key < curent->key) {
            if (curent->left == NULL) { curent->left = new node(key,curent); break; }
            else curent = curent->left;
        } else
        {
            if (curent->right == NULL) { curent->right = new node(key, curent); break; }
            else curent = curent->right;
        }
    }
    GetBalance(curent);
}



void dfs(node * A)
{
    if (A == NULL) return;
    cout << A->key << " ";
    if (A->left) cout << A->left->key << "-l ";
    if (A->right) cout << A->right->key << "-r ";
    cout << endl;

      dfs(A->left);
     dfs(A->right);
}

void Sterge(node * A)
{
    if (A == NULL) return;
    // nici un fiu
    if (A->left == NULL && A->right == NULL) {
        node *par = A->parent;
        if (par) {
            if (par->left == A) par->left = NULL; else par->right = NULL;
            GetBalance(par);
        }
        return;
    }
    // doar fiul drept
    if (A->left == NULL) {
        node * par = A->parent;
        node * son = A->right;
        if (A == root) {
            root = A->right;
        } else {
            if (par->left == A) par->left = son; else par->right = son;
            son->parent = par;
            GetBalance(par);
        }
        return;
    }
    // doar fiul stang
    if (A->right == NULL) {
        node * par = A->parent;
        node * son = A->left;
        if (A == root) {
            root = A->right;
        } else {
            if (par->left == A) par->left = son; else par->right = son;
            son->parent = par;
            GetBalance(par);
        }
        return;
    }
    // ambii fii
    node * succ = A->right;
    while (succ->left) succ = succ->left;

    A->key = succ->key;
    Sterge(succ);

}

int main()
{
    freopen("hashuri.in","r",stdin);
    freopen("hashuri.out","w",stdout);

    int N, val, type;
    cin >> N;


    while (N--)
    {
        cin >> type >> val;
        if (type == 1) Insereaza(val);
        if (type == 3) cout << (inAVL(val) != NULL) << endl;
        if (type == 2) Sterge(inAVL(val));
     //   dfs(root);cout<<endl<<endl;
    }

    return 0;

}