#include <iostream>
#include <fstream>
using namespace std;
template <class T>
class ABC
{
private:
	int n;
	
	struct nod
	{
		T info;
		nod* left;
		nod* right;
	};

	nod* start;
public:
	ABC();
	void adaugare(T x);
	void stergere(T x);
	int cautare(T x);
	void srd(nod* p);
	void afisare();
	void inserare(nod*& p, T x);
};

template <class T>
ABC<T>::ABC()
{
	start = NULL;
}

/*template <class T>
void ABC<T>::adaugare(T x)
{
	if (start == NULL)
	{
		start = new nod;
		start->info = x;
		start->left = NULL;
		start->right = NULL;
	}
	else
	{
		nod* p = start;
		bool found = false;
		while (p != NULL)
		{
			if (x < p->info)
				p = p->left;
			else
			if (x > p->info)
				p = p->right;
			else
				if (x == p->info)
				{
					found = true;
					break;
				}
		}
		if (found == true)
			return;
		else
		{
			p = new nod;
			p->info = x;
			p->left = NULL;
			p->right = NULL;
		}
	}
}*/

template <class T>
void ABC<T>::adaugare(T x)
{
	inserare(start, x);
}

template <class T>
void ABC<T>::inserare(nod*& p, T x)
{
	if (p == NULL)
	{
		p = new nod;
		p->info = x;
		p->left = NULL;
		p->right = NULL;
	}
	else
		if (x < p->info)
			inserare(p->left, x);
		else if(x > p->info)
			inserare(p->right, x);
		else return;
}

template <class T>
int ABC<T>::cautare(T x)
{
	if (start == NULL)
		return 0;
	nod* p = start;
	while (p != NULL && p->info != x)
	{
		if (x < p->info)
			p = p->left;
		else
		if (x > p->info)
			p = p->right;
	}
	if (p == NULL)
		return 0;
	return 1;
}

template <class T>
void ABC<T>::stergere(T x)
{
	if (this->cautare(x) == 0)
		return;
	if (x == start->info)
	{
		if (start->left == NULL && start->right == NULL)
			delete start, start = NULL;
		if (start->left != NULL && start->right == NULL)
		{
			nod* p = start->left;
			delete start;
			start = p;
		}
		if (start->left == NULL && start->right != NULL)
		{
			nod* p = start->right;
			delete start;
			start = p;
		}
		if (start->left != NULL && start->right != NULL)
		{
			nod* p = start->left;
			if (p->right == NULL)
			{
				p->right = start->right;
				delete start;
				start = p;
			}
			else
			{
				nod* q = p->right;
				while (q->right != NULL)
					p = p->right, q = q->right;
				p->right = q->left;
				q->right = start->right;
				q->left = start->left;
				delete start;
				start = q;
			}
		}
	}
	else
	{
		nod* p;
		nod* r;
		nod* q;
		nod* z;
		int d;
		p = start;
		if (x<p->info)
			r = p->left;
		else r = p->right;
		while (r->info != x)
			if (x<r->info)
			{
				p = r; r = r->left;
			}
			else { p = r; r = r->right; }
			if (r->left == NULL && r->right == NULL)
			{
				if (r->info<p->info)
				{
					p->left = NULL;
					delete r;
				}
				else
				{
					p->right = NULL;
					delete r;
				}
			}
			else if (r->left == NULL && r->right != NULL)
			{
				if (r->info<p->info)
				{
					p->left = r->right;
					delete r;
				}
				else
				{
					p->right = r->right;
					delete r;
				}
			}
			else if (r->left != NULL && r->right == NULL)
			{
				if (r->info<p->info)
				{
					p->left = r->left;
					delete r;
				}
				else
				{
					p->right = r->left;
					delete r;
				}
			}
			else if (r->left != NULL && r->right != NULL)
			{
				q = r;
				z = r->left;
				d = -1;
				while (z->right != NULL)
				{
					q = z;
					z = z->right;
					d = 1;
				}
				r->info = z->info;
				if (d<0)
				{
					q->left = z->left;
					delete z;
				}
				else
				{
					q->right = NULL;
					delete z;
				}
			}

	}
}

template <class T>
void ABC<T>::srd(nod* p)
{
	if (p != NULL)
		{

			srd(p->left);
			cout << p->info << " ";
			srd(p->right);
		}
}

template <class T>
void ABC<T>::afisare()
{
	nod* p = start;
	srd(p);
}

int main()
{
	ifstream f("hashuri.in");
	ofstream g("hashuri.out");
	ABC<int> abc;
	int n,x,op,i;
	f >> n;
	for (i = 0; i < n; i++)
	{
		f >> op >> x;
		if (op == 1)
			abc.adaugare(x);
		if (op == 2)
			abc.stergere(x);
		if (op == 3)
			g << abc.cautare(x) << "\n";
		abc.afisare();
		cout << endl;
	}
	return 0;
}