Найти сумму 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 наименьших элементов в бинарном дереве поиска.

Примеры