You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

QAQ作为车库的管理人员，他管理的车库有以下三个特点：

1， 只有一个门

2， 长度无限长

3， 车库的宽度正好能单辆小车入库或者出库，既车库不能够并排多辆小车、

每辆进入车库的小车都一样，只是小车的价值不一样。

他老板每次询问QAQ，车库里面价值最高的小车的价值是多少，由于工作量比较大，QAQ需要你的帮忙、

Format

Input

有多组测试案例. 第一行输入一个数K，表示有K次操作(1<=K<=1,000,000).

接下来有K行，每行输入有三种形式：

1 v 表示此时车库进入一辆价值为v的小车(1<=v<1,000,000,000)

2 表示此时车库有一辆小车出库

3 表示询问小明此时车库里面价值最大的小车的价值是多少,如果车库里面没有小车,则输出-1

Output

对于每次询问，输出车库中价值最大的车，如果没有小车，则输出-1

Samples

6
1 3
1 2
1 4
3
2
3

4
3

Limitation

1s, 1024KiB for each test case.