Найти сумму k наименьших элементов в BST

Предположим, у нас есть пустое бинарное дерево поиска (BST), в котором пока нет ни одного узла. Нам нужно выполнить два типа запросов:

  1. insert x — вставить значение x в BST.

  2. sum k — вывести сумму k самых маленьких элементов в BST.

Пусть всего имеется q запросов. Задача — написать программу, которая обработает все эти запросы.

Входные данные

В первой строке входных данных содержится одно число q (1 ≤ q ≤ 1000).

В следующих q строках записаны запросы. Для всех запросов вида insert значение x по модулю не превышает . Для всех запросов вида sum значение k не больше текущего размера дерева.

Выходные данные

Для каждого запроса sum необходимо вывести сумму k наименьших элементов в бинарном дереве поиска.

Примеры

Входные данные

Выходные данные

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