#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

struct node {
    int key;
    node *l;
    node *r;
    node *prev;
};

node* find(node *peak, int key);

void insert(node **root, int key) {
    if (find(*root, key) != NULL)
    {
        return;
    }

    node *q;
    q = new node();
    q->key = key;
    q->l = NULL;
    q->r = NULL;
    q->prev = NULL;
    node *cur = *root;

    while (cur != NULL)
    {
        if (key == cur->key)
        {
            return;
        }
        if (key > cur->key)
        {
            if (cur->r != NULL)
            {
                cur = cur->r;
            } else {
                q->prev = cur;
                cur->r = q;
                return;
            }
        } else if (key < cur->key)
        {
            if (cur->l != NULL) {
                cur = cur->l;
            } else {
                q->prev = cur;
                cur->l = q;
                return;
            }
        }
    }

    *root = q;
}

node* find(node *peak, int key) {
    if (peak == NULL || peak->key == key)
    {
        return peak;
    }
    if (key < peak->key)
    {
        return find(peak->l, key);
    } else {
        return find(peak->r, key);
    }
}

node* next(node *root, int x)
{
    node *cur = root;
    node *result = NULL;
    while(cur != NULL)
    {
        if (cur->key > x)
        {
            result = cur;
            cur = cur->l;
        } else {
            cur = cur->r;
        }
    }
    return result;
}

void del(node *root, int key)
{
    node* peak = find(root, key);
    if (peak == NULL)
    {
        return;
    }

    if (peak == root) {
        if (peak->l == NULL && peak->r == NULL)
        {
            root = NULL;
            delete peak;
            return;
        }

        if (peak->l == NULL || peak->r == NULL)
        {
            if (peak->l == NULL)
            {
                root = peak->r;
            } else {
                root = peak->l;
            }
            delete peak;
            return;
        }
    }

    if (peak->l == NULL && peak->r == NULL) {
        if (peak->prev->l == peak)
        {
            peak->prev->l = NULL;
        }
        if (peak->prev->r == peak)
        {
            peak->prev->r = NULL;
        }
        delete peak;
        return;
    }

    if (peak->l == NULL || peak->r ==  NULL) {
        if (peak->l == NULL) {
            if (peak->prev->l == peak)
            {
                peak->prev->l = peak->r;
            } else {
                peak->prev->r = peak->r;
            }
            peak->r->prev = peak->prev;
        } else {
            if (peak->prev->l == peak)
            {
                peak->prev->l = peak->l;
            } else {
                peak->prev->r = peak->l;
            }
            peak->l->prev = peak->prev;
        }
        delete peak;
        return;
    }

    node* cur = next(root, key);
    peak->key = cur->key;
    if (cur->prev->l == cur)
    {
        cur->prev->l = cur->r;
        if (cur->r != NULL)
        {
            cur->r->prev = cur->prev;
        }
    } else {
        cur->prev->r = cur->r;
        if (cur->r != NULL)
        {
            cur->r->prev = cur->prev;
        }
    }
    delete cur;
}

node* prev(node *root, int x)
{
    node *cur = root;
    node *result = NULL;
    while(cur != NULL)
    {
        if (cur->key >= x)
        {
            cur = cur->l;
        } else {
            result = cur;
            cur = cur->r;
        }
    }
    return result;
}


int main()
{
    node *root = NULL;
    ifstream fin("bstsimple.in");
    ofstream fout("bstsimple.out");
    string command;
    int x;
    while( fin >> command )
    {
        if (command == "insert")
        {
            fin >> x;
            insert(&root, x);
        } else if (command == "delete")
        {
            fin >> x;
            del(root, x);
        } else if (command == "exists")
        {
            fin >> x;
            if (find(root, x) != NULL)
            {
                fout << "true\n";
            } else {
                fout << "false\n";
            }
        } else if (command == "prev")
        {
            fin >> x;
            node *q = prev(root, x);
            if (q != NULL)
            {
                fout << q->key << endl;
            } else {
                fout << "none\n";
            }
        } else if (command == "next")
        {
            fin >> x;
            node *q = next(root, x);
            if (q != NULL)
            {
                fout << q->key << endl;
            } else {
                fout << "none\n";
            }
        }
    }

    return 0;
}