Description

并行处理中的编程范型之一是生产者/消费者范型，可以使用具有管理者进程和多个客户进程的系统来实现。客户可以是生产者、消费者等，管理者跟踪客户进程。每个进程都有一个成本（正整数，范围是 $1～10 000$ ）。具有相同成本的进程数不能超过 $10 000$ 。队列根据三种类型的请求进行管理，如下所述。

• a x ：将成本为 $x$ 的进程添加到队列中。
• r ：根据当前管理者策略从队列中删除进程（如果可能）。
• p i ：执行管理者的策略 $i$ ，其中 $i$ 是 $1$ 或 $2$ 。$1$ 表示删除最小成本进程；$2$ 表示删除最大成本进程。默认管理者策略为 $1$。
• e ：结束请求列表。 只有在删除列表中包含已删除进程的序号时，管理者才会输出已删 除进程的成本。编写一个程序来模拟管理者进程。

Format

Input

输入中的每个数据集都有以下格式。

• 进程的最大成本。

• 删除列表的长度。

• 删除列表。查询已删除进程的序号列表；例如$1$ $4$，表示查询第$1$个和第$4$个已删除进程的成本。

• 每个请求列表，各占一行。

每个数据集都以 $e$ 请求结束。数据集以空行分隔。

Output

如果删除请求的序号在列表中，并且此时队列不为空，则 单行输出删除的每个进程的成本。如果队列为空，则输出 $-1$ 。以空行分隔不同数据集的结果。

Samples

5
2
1 3
a 2
a 3
r
a 4
p 2
r
a 5
r
e

2
5