Description

学校有一个任务调度中心，需要管理学生提交的任务。

每个任务包含两个属性：

• id：任务编号，保证全局唯一。
• priority：任务优先级，数值越大，优先级越高。 现在有 q 次操作，需要你维护任务调度中心。

支持以下四种操作：

操作 1：添加任务 ·1 id priority

向调度中心添加一个编号为 id、优先级为 priority 的任务。

保证每个任务编号只会被添加一次。

操作 2：取消任务 ·2 id

取消编号为 id 的任务。

如果该任务不存在或者已经被执行、取消，则不进行任何操作。

操作 3：执行任务 ·3

从当前所有未执行、未取消的任务中，选择优先级最高的任务执行，并输出它的编号和优先级。

如果存在多个优先级相同的任务，则选择编号最小的任务。

如果当前没有任务，输出 -1。

执行后，该任务从调度中心中删除。

操作 4：查询最小编号 ·4

查询当前所有未执行、未取消的任务中编号最小的任务，并输出它的编号。

注意：该操作只查询，不会执行或者删除任务。

如果当前没有任务，输出 -1。

Format

Input

第一行输入一个整数 q，表示操作次数。

接下来 q 行，每行表示一种操作。 数据范围

1 <= q <= 2e5

1 <= id,priority <= 1e9

保证每个任务编号最多添加一次。

Output

对于每次操作 3 和操作 4，按照题目要求输出结果。

Samples

11
1 10 5
1 20 8
1 15 8
4
3
2 20
3
3
1 7 10
4
3

10
15 8
10 5
-1
7
7 10

Limitation

1s, 1024KiB for each test case.