Binary Search Tree 2

Input

The input file contains a series of operations to be performed on the tree, with the total number of operations not exceeding $100000$. 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 smallest 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.

Examples