# include <bits/stdc++.h>

using namespace std;

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

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

node * root = NULL;

int get_height(node * A){
    return A == NULL ? -1 : A->height;
}

void calculate_height(node *A) {
    A->height = 1 + max(get_height(A->left), get_height(A->right));
}
void RotateLeft(node *& B, int verif);
void RotateRight(node *& A, int verif = 1)
{
    node * par = A->parent;
    node * B = A->left;

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

        if (hr > hl) RotateLeft(B,0);
        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;

    calculate_height(A);
    calculate_height(B);

    A = B;
}

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

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

        if (hl > hr) RotateRight(A,0);
        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;

    calculate_height(A);
    calculate_height(B);

    B = A;
}

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


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

        curent = curent->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;
        }
    }
    node  * tmp = curent;
    while (tmp) calculate_height(tmp), tmp = tmp->parent;

    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);

}

void Preordine(node * A)
{
    if (A == NULL) return;
    Preordine(A->left);
    cout << A->key << " ";
    Preordine(A->right);
}

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

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


    while (N--)
    {
        scanf("%d%d", &type, &val);
        if (type == 1) Insereaza(val);
        if (type == 3) printf("%d\n", (int)(inAVL(val) != NULL) );
        if (type == 2) Sterge(inAVL(val));
     //   dfs(root);cout<<endl<<endl;
    }
    // Preordine(root);
    return 0;

}