Двійкове дерево пошуку 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. Слідуйте формату вихідного файла з прикладу.