Алгоритмы и структуры данных

Максимальное значение в BST (бинарном дереве поиска)

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

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

  2. max — вывести максимальное значение в BST

  3. print — вывести BST в порядке обхода in-order (симметричный обход).

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

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

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

Следующие q строк содержат запросы. Во всех запросах вида insert значение x не превосходит по модулю .

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

Для каждого запроса max выведите на отдельной строке максимальное значение в BST.

Для каждого запроса print выведите результат обхода BST в post-order (значения должны быть разделены пробелом).

Примеры

Input

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

7
insert 2
insert 1
max
insert 0
max
insert 4
print

7
insert 2
insert 1
max
insert 0
max
insert 4
print

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