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.