K. K-я строка словаря

1000 мс · 256 МБ · всё или ничего

Реализуйте словарь с двумя операциями: добавить строку и вывести $k$ -ю строку в лексикографическом порядке.

Формат ввода

В первой строке - число команд $N$ ( $1 \le N \le 10^5$ ).

Далее $N$ строк: «1 S» - добавить строку $S$ ; «2 k» - вывести $k$ -ю строку. Строки состоят из строчных латинских букв, суммарная длина добавляемых строк не превосходит $3 \cdot 10^5$ . Запрашиваемая строка всегда существует.

Формат вывода

Для каждого запроса второго типа выведите строку.

Примеры

ввод

7
1 pushkin
1 lermontov
1 tolstoy
1 gogol
1 gorkiy
2 5
2 1

вывод

tolstoy
gogol

ввод

3
1 aba
1 aba
2 2

вывод

aba

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.