#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

struct tree {
	int k, l, r, p;
};
int i, x;
tree v[20000005];


void ins(int x, int j, int kol)
{
	if (v[j].k > x && v[j].l == 0)
	{
		v[j].l = kol;
		v[kol].k = x;
		v[kol].p = j;
		exit;
	}
	if (v[j].k < x && v[j].r == 0)
	{
		v[j].r = kol;
		v[kol].k = x;
		v[kol].p = j;
		exit;
	}
	if (v[j].k > x)
		ins(x, v[j].l, kol);
	if (v[j].k < x)
		ins(x, v[j].r, kol);
}

void del(int j, int x)
{
	if (x > v[j].k)
	{
		if (v[j].r != 0)
			del(v[j].r, x);
		return;
	}
	if (x < v[j].k)
	{
		if (v[j].l != 0)
			del(v[j].l, x);
		return;
	}
	if (v[j].l == 0 && v[j].r == 0)
	{
		if (v[v[j].p].l == j)
			v[v[j].p].l = 0;
		else
			v[v[j].p].r = 0;
		return;
	}
	if (v[j].r == 0)
	{
		if (v[v[j].p].l == j)
			v[v[j].p].l = v[j].l;
		else
			v[v[j].p].r = v[j].l;
		return;
	}
	else
	{
		int h = v[j].r;
		while (v[h].l != 0)
			h = v[h].l;
		v[j].k = v[h].k;
		del(h, v[h].k);
	}
}

bool ex(int x, int j)
{
	if (v[j].k == x) return 1;
	if ((x > v[j].k and v[j].r == 0) || (x < v[j].k and v[j].l == 0)) return 0;
	if (x > v[j].k) return ex(x, v[j].r);
	if (x < v[j].k) return ex(x, v[j].l);
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("bstsimple.in", "r", stdin);
	//freopen("bstsimple.out", "w", stdout);
	string str;
	int kol = 0;
	while (cin >> str)
	{
		cin >> x;
		if (str == "insert")
		{
			kol++;
			if (kol == 1)
			{
				v[kol].k = x;
				continue;
			}
			ins(x, 1, kol);
		}
		if (str == "delete")
		{
			del(1, x);
		}

		if (str == "exists")
		{
			if (ex(x, 1))
				cout << "true\n";
			else
				cout << "false\n";
		}

		if (str == "next")
		{
			bool f = 1, f2 = 1;
			int j = 1, suc = 0;
			while (j != 0)
				if (v[j].k > x)
				{
					f2 = 0;
					suc = j;
					j = v[j].l;
				}
				else if (v[j].r == 0 && f2)
				{
					f = 0;
					cout << "none\n";
					break;
				}
				else
					j = v[j].r;
			if (f)
				cout << v[suc].k <<"\n";
		}

		if (str == "prev")
		{
			bool f = 1, f2 = 1;
			int j = 1, suc = 0;
			while (j != 0)
				if (v[j].k < x)
				{
					f2 = 0;
					suc = j;
					j = v[j].r;
				}
				else if (v[j].l == 0 && f2)
				{
					f = 0;
					cout << "none\n";
					break;
				}
				else
					j = v[j].l;
			if (f)
				cout << v[suc].k << "\n";
		}
	}
	return 0;
}
/*
insert 100
insert 50
insert 150
insert 130
insert 140
insert 120
delete 130
insert 140
insert 110
insert 135
insert 145
insert 136
insert 134
insert 132
insert 125
insert 105
*/