Encontre a soma dos k menores elementos em uma BST (árvore binária de pesquisa)

Dada uma árvore binária de pesquisa vazia, sem quaisquer nós, você precisa executar 2 tipos de consultas:

1. insert x – insere o valor x na BST

2. sum k – exibe a soma dos k menores elementos na BST

Sendo q o número de consultas, você deve escrever um programa para executar essas consultas.

Entrada

A primeira linha da entrada contém um único 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 sum, o valor de k não excede o tamanho atual da árvore.

Saída

Para cada consulta sum, o programa deve imprimir a soma dos k menores elementos na árvore binária de pesquisa.

Exemplos