Given an empty binary search tree with no nodes, you are asked to perform 2 kinds of queries:

insert x - insert the value x in the BST

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