Найти k-ое по величине значение в BST

Дано пустое дерево поиска без каких-либо узлов. Необходимо выполнить два вида запросов:

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

2. smallest k — вывести k-ый по величине элемент в BST.

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

Ввод

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

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

Вывод

Для каждого запроса smallest необходимо вывести k-ый по величине элемент в двоичном дереве поиска.

Примеры