Encontre o k-ésimo menor valor em uma BST

Dada uma árvore binária de pesquisa (BST) vazia, sem nós, você precisa realizar dois tipos de consultas:

1. insert x – insere o valor x na BST

2. smallest k – exibe o k-ésimo menor elemento na BST

Dadas q consultas, você deve escrever um programa para processar todas elas.

Entrada

A primeira linha da entrada contém um número q (1 ≤ q ≤ 1000).

As próximas q linhas contêm as consultas. Para todas as consultas insert, o valor de x não excede em valor absoluto. Para todas as consultas smallest, o valor de k não excede o tamanho atual da árvore.

Saída

Para cada consulta smallest, o programa deve imprimir o k-ésimo menor valor na BST.

Exemplos