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

Eingabe

Ausgabe

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