Андрюша — юный инженер. Сейчас он конструирует современный автомат для преобразования чисел. В процессе конструирования к автомату добавляются все новые и новые блоки, и Андрюше интересно, как будет работать автомат после каждой такой модификации.
Автомат представляет собой последовательность из блоков двух типов: максимизаторов и минимизаторов . На каждом блоке написано некоторое натуральное число x . Максимизатор принимает на вход натуральное число a и подает на выход число max ( x , a ) . Минимизатор принимает на вход натуральное число a и подает на выход число min ( x , a ) .
Автомат работает следующим образом: он принимает некоторое натуральное число, которые подает на вход первому блоку, затем то, что получилось на выходе у первого блока, подается на вход второго блока, и так далее. В итоге автомат возвращает число, получившееся на выходе у последнего блока. Иначе говоря, автомат просто последовательно пропускает данное ему число через все блоки.
Изначально в автомате нет ни одного блока, и он просто возвращает число, которое принимает.
Андрюша последовательно выполняет действия с автоматом. Действия бывают трех типов:
- Добавить в конец последовательности блоков автомата максимизатор, на котором написано число x .
- Добавить в конец последовательности блоков автомата минимизатор, на котором написано число x .
- Подать на вход автомату число x . В этом случае Андрюша хочет узнать, что автомат вернет на выход.
Андрюша уже запланировал, какие действия и в каком порядке он будет совершать. Напишите программу, которая определит результат работы автомата Андрюши, чтобы он мог убедиться в его исправности!
Входные данные
Первая строка входных данных содержит единственное целое число n ( 1 ≤ n ≤ 4·10
5 ) — суммарное количество действий Андрюши.
В каждой из следующих n строк содержится по два целых числа t и x ( 1 ≤ t ≤ 3 , 1 ≤ x ≤ 10
9 ), где t — это тип очередного действия. Если t = 1 , то Андрюша хочет добавить к автомату максимизатор, на котором написано число x . Если t = 2 , то Андрюша хочет добавить к автомату минимизатор, на котором написано число x . Если t = 3 , то Андрюша хочет подать на вход автомату число x и узнать, что получится на выходе.
Выходные данные
Для каждого действия третьего типа выведите в отдельной строке одно число, которое должно получиться на выходе автомата после этого действия.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
7
3 5
1 5
3 2
3 7
2 7
3 8
3 6 |
5
5
7
7
6 |