Trova la somma dei k elementi minori in un BST

Dato un Binary Search Tree (BST, albero di ricerca binario) inizialmente vuoto e senza nodi, ti viene chiesto di eseguire 2 tipi di query:

1. insert x – inserisce il valore x nel BST

2. sum k – stampa la somma dei k elementi più piccoli presenti nel BST

Avendo q query, l’obiettivo è scrivere un programma che esegua queste operazioni.

Input

La prima riga dell’input contiene un singolo numero q (1 ≤ q ≤ 1000).

Le successive q righe contengono le query. Per tutte le query di tipo insert, il valore di x non supera in valore assoluto. Per tutte le query di tipo sum, il valore di k non è più grande della dimensione corrente dell’albero.

Output

Per ogni query di tipo sum, il programma deve stampare la somma dei k elementi più piccoli presenti nel BST.

Esempi