BSTでk個の最小要素の合計を求める

何もノードが存在しない空のBinary Search Tree (BST) を用意し、次の2種類のクエリを実行するよう求められています:

1. insert x - BSTに値xを挿入する

2. sum k - BSTの中から最も小さい要素k個の合計を出力する

クエリがq個与えられるので、これらのクエリを処理するプログラムを書いてください。

入力

最初の行には、整数q (1 ≤ q ≤ 1000) が与えられます。

続くq行にはクエリが与えられます。すべてのinsertクエリで挿入されるxの絶対値はを超えません。また、sum kクエリのkは、常に現在のBSTのサイズ以下になります。

出力

各sum kクエリに対して、BSTの中で最も小さい要素k個の合計を1行に出力してください。

例