Encontrar el valor k-ésimo más pequeño en un BST

Dado un árbol de búsqueda binaria (BST) vacío sin ningún nodo, se solicitan 2 tipos de consultas:

1. insert x - insertar el valor x en el BST

2. smallest k - imprimir el elemento k-ésimo más pequeño en el BST

Dadas q consultas, se pide escribir un programa que ejecute estas operaciones.

Entrada

La primera línea de la entrada contiene un único número q (1 ≤ q ≤ 1000).

Las siguientes q líneas contienen consultas. Para todas las consultas insert, el valor de x no supera en valor absoluto. Para todas las consultas smallest, el valor de k no excede el tamaño actual del árbol.

Salida

Para cada consulta smallest, el programa debe imprimir el elemento k-ésimo más pequeño en el árbol de búsqueda binaria.

Ejemplos