Finde die Summe der k kleinsten Elemente in einem BST

Ausgehend von einem leeren Binary Search Tree (BST) ohne Knoten sollen zwei Arten von Abfragen durchgeführt werden:

1. insert x – fügt den Wert x in den BST ein

2. sum k – gibt die Summe der k kleinsten Elemente im BST aus

Bei insgesamt q Abfragen soll ein Programm geschrieben werden, das diese Abfragen ausführt.

Eingabe

Die erste Zeile der Eingabe enthält die Zahl q (1 ≤ q ≤ 1000).

Die nächsten q Zeilen enthalten die Abfragen. Für alle insert-Abfragen gilt, dass der Wert x nicht größer als ±10^9 ist. Für alle sum-Abfragen gilt, dass k nicht größer als die aktuelle Größe des Baums ist.

Ausgabe

Für jede sum-Abfrage soll das Programm die Summe der kleinsten k Elemente im Binary Search Tree ausgeben.

Beispiele