该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

ボクは生まれ　そして気づく

所詮　ヒトの真似事だと

知ってなおも歌い続く

永遠（トワ）の命

「VOCALOID」

DengDuck十分爱听初音的歌，他收获了美好的一天

可惜，转眼间，一场比赛即将结束，初音未来将要离开了......

题目描述

不过还有一道简单题捏

你要实现一个数据结构，可以执行以下操作

• Push x 添加一个值为 x 的元素
• Delete x 删除所有值为 x 的元素
• Pop 1 输出最后一个添加的元素的值并弹出该元素
• Pop 2 输出最前一个添加的元素的值并弹出该元素
• Pop 3 输出值最大的元素的值并弹出该元素,如果有多个最大值，弹出先添加的
• Pop 4 输出值最小的元素的值并弹出该元素，如果有多个最小值，弹出后添加的

输入格式

输入一个整数$n$，表示有$n$次操作

接下来$n$行每行读如一个字符串$s$和一个数字$x$表示操作，意义见题面描述

输出格式

对于所有的Pop操作，输出对应的答案，一行一个

数据保证没有“没有元素但依然需要弹出”的情况

4
Push 1
Push 2
Push 3
Pop 3

3

9
Push 8
Push 6
Pop 1
Push 4
Push 1
Pop 1
Push 7
Pop 2
Pop 4

6
1
8
4

14
Push 2
Pop 4
Push 1
Pop 2
Push 6
Delete 7
Pop 1
Push 2
Push 7
Push 1
Delete 6
Pop 2
Pop 1
Pop 1

2
1
6
2
1
7

提示

对于$10\%$的数据，$1\leq n\leq 100$

对于$30\%$的数据，$1\leq n\leq 10^3$

对于$50\%$的数据，$1\leq n\leq 10^4$

对于$100\%$的数据，$1\leq n\leq 5*10^5$

保证$s$的值只可能是Push，Delete或Pop

如果$s$为Push,$1\leq x \leq 10^7$

如果$s$为Pop,$1\leq x \leq 4$