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

Input

Output

8
insert 2
insert 1
sum 1
sum 2
insert 10
insert 20
sum 3
sum 2

1
3
13
3

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue