Двоичное дерево поиска 2
Реализуйте сбалансированное двоичное дерево поиска.
Входные данные
Входной файл содержит описание операций с деревом, их количество не превышает 100000. Формат операций смотрите в предыдущей задаче. В каждой строке находится одна из следующих операций:
insert x - добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не надо.
delete x - удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не надо.
exists x - если ключ x есть в дереве, выведите "true", иначе "false".
next x - выведите минимальный элемент в дереве, строго больший x, или "none", если такого нет.
prev x - выведите максимальный элемент в дереве, строго меньший x, или "none", если такого нет.
kth k - выведите k-ый по величине элемент (нумерация с единицы). Если такого не существует, то выведите "none".
Все числа во входном файле целые и по модулю не превышают 10^9.
Выходные данные
Выведите последовательно результат выполения всех операций exists, next, prev. Следуйте формату выходного файла из примера.