Binary Search Tree 2
Implement a balanced binary search tree.
Input
The input file contains a series of operations to be performed on the tree, with the total number of operations not exceeding 100,000. The format for these operations is detailed in the previous problem. Each line will specify one of the following operations:
insert x - Add the key x to the tree. If x is already present, do nothing.
delete x - Remove the key x from the tree. If x is not present, do nothing.
exists x - Check if the key x is in the tree. Output "true" if it is, otherwise output "false".
next x - Output the smallest element in the tree that is strictly greater than x, or "none" if no such element exists.
prev x - Output the largest element in the tree that is strictly less than x, or "none" if no such element exists.
kth k - Output the k-th largest element (indexing starts from one). If there is no such element, output "none".
All numbers in the input are integers and do not exceed 10^9 in absolute value.
Output
Provide the results of all exists, next, and prev operations in the order they are processed. Follow the output format as shown in the example.