Двоичное дерево поиска 2

Input

Входной файл содержит описание операций с деревом, их количество не превышает 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.

Output

Выведите последовательно результат выполения всех операций exists, next, prev. Следуйте формату выходного файла из примера.

Examples