Algorithms and Data Structures

Find the sum of k smallest elements in a BST

Given an empty binary search tree with no nodes, you are asked to perform 2 kinds of queries:
  1. insert x - insert the value x in the BST
  1. sum k - print the sum of k smallest elements in the BST
Given q queries, you are asked to write a program to perform these queries.

Input

The first line of the input contains a single number q (1 ≤ q ≤ 1000).
The next q lines contain queries. For all the insert queries, the value of x does not exceed in absolute value. For all the sum queries, the value of k does not exceed the current tree size.

Output

For each sum query, the program should print the sum of the smallest k elements in the binary search tree.

Examples

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