#include <iostream>

struct Node{
    int key;
    Node* left = nullptr;
    Node* right = nullptr;
    Node* parent = nullptr;
    Node(int k, Node* l = nullptr, Node* r = nullptr, Node* p = nullptr){
        key = k;
        left = l;
        right = r;
        parent = p;
    }
};
void set_parent(Node * child, Node* parent){
    if (child != nullptr){
        child->parent = parent;
    }
}

void keep_parent(Node* parent){
    set_parent(parent->left, parent);
    set_parent(parent->right, parent);
}

void rotate(Node* parent, Node* child){
    Node* grantpar = child->parent->parent;
    if(grantpar != nullptr){
        if(grantpar->left == parent){
            grantpar->left = child;
        }else{
            grantpar->right = child;
        }
        }
    if(parent->left == child){
        parent->left = child->right;
        child->right = parent;
    }else{
        parent->right = child->left;
        child->left = parent;
    }
    keep_parent(parent);
    keep_parent(child);
    child->parent = grantpar;
}

Node* splay(Node* node){
    if(node->parent == nullptr){
        return node;
    }
    Node* parent = node->parent;
    Node* grant_parent = node->parent->parent;
    if (grant_parent == nullptr){
        rotate(parent, node);
        return node;
    }
    else{
        if((grant_parent->left == parent) == (parent->left == node)){
            rotate(grant_parent, parent);
            rotate(parent,node);
        }else{
            rotate(parent, node);
            rotate(grant_parent, node);
        }
        return splay(node);
    }
}

Node* find(Node* node, int key){
    if(node == nullptr){
        return node;
    }
    else if(node->key > key){
        if(node->right == nullptr){
            splay(node);
        }else{
            return find(node->right, key);
        }
    }
    else if(node->key < key){
        if(node->left == nullptr){
            splay(node);
        }else{
            return find(node->left, key);
        }
    }
    return splay(node);
}

Node* subtree_max(Node* node){
    if(node->right != nullptr){
        return subtree_max(node->right);
    }else{
        splay(node);
    }
}

Node* subtree_min(Node* node){
    if(node->left != nullptr){
        return subtree_min(node);
    }else{
        splay(node);
    }
}

Node* merge(Node* left, Node* right){
    if(right == nullptr){
        return left;
    }
    if(left == nullptr){
        return right;
    }
    right = find(right, left->key);
    right->left = left;
    left->parent = right;
    return right;
}

std::pair<Node*, Node*>split(Node* root, int key){
    if(root == nullptr){
        return std::make_pair(nullptr, nullptr);
    }
    root = find(root, key);
    if(root->key <= key){
        if (root->right != nullptr){
            root->right->parent = nullptr;
            root->right = nullptr;
            return std::make_pair(root, root->right);
        }
        else{
            return std::make_pair(root, nullptr);
        }
    }
    else{
        if(root->left != nullptr){
            root->left->parent = nullptr;
            root->left = nullptr;
            return std::make_pair(root, root->left);
        }
        else{
            return std::make_pair(root, nullptr);
        }
    }
}

Node* insert(Node* node, int key){
    std::pair<Node*, Node*> subtrees = split(node,key);
    Node* left_node = subtrees.first;
    Node* right_node = subtrees.second;
    if((left_node!= nullptr)&&(left_node->key == key)){
        left_node->right = right_node;
        keep_parent(left_node);
        return left_node;
    }
    if((right_node != nullptr)&&(right_node->key == key)){
        right_node->left = left_node;
        keep_parent(right_node);
        return right_node;
    }
    Node* newnode = new Node(key, left_node, right_node);
    keep_parent(newnode);
    return newnode;
}

Node* remove(Node* node, int key){
    node = find(node, key);
    if((node != nullptr) && (node->key == key)){
        if(node->left != nullptr){
            node->left->parent = nullptr;
        }
        if(node->right != nullptr){
            node->right->parent = nullptr;
        }
        node = merge(node->left, node->right);
    }
    return node;
}

Node* prev_el(Node* root, int key){
    root = find(root, key);
    if(root != nullptr){
        if(root->key < key){
            return root;
        }else if(root->left != nullptr){
            root = subtree_max(root->left);
            return root;
        }
    }else{
        return nullptr;
    }

}

Node* next_el(Node* root, int key){
    root = find(root, key);
    if(root != nullptr){
        if(root->key > key){
            return root;
        }else if(root->right != nullptr){
            root = subtree_min(root->right);
            return root;
        }
    }else{
        return nullptr;
    }

}

int main() {
    Node* root = nullptr;
    while(std::cin){
        std::string command = " ";
        std::cin >> command;
        if(command == "insert"){
            int key = 0;
            std::cin >> key;
            root = insert(root, key);
            std::cout << root->key;
        }
        if(command == "delete"){
            int key = 0;
            std::cin >> key;
            root = remove(root, key);
        }
        if(command == "exists"){
            int key = 0;
            std::cin >> key;
            root = find(root, key);
            if(root != nullptr && root->key == key){
                std::cout << "true" <<'\n';
            }else{
                std::cout << "false" <<"\n";
            }
        }
        if(command == "next"){
            int key = 0;
            std::cin >> key;
            root = next_el(root, key);
            if(root != nullptr && root->key == key){
                std::cout << root->key <<'\n';
            }else{
                std::cout << "none" <<"\n";
            }
        }
        if(command == "prev"){
            int key = 0;
            std::cin >> key;
            root = prev_el(root, key);
            if(root != nullptr && root->key == key){
                std::cout << root->key <<'\n';
            }else{
                std::cout << "none" <<"\n";
            }

        }
    }
    return 0;
}