排队羊（queue）

问题背景

咩咩国的喜羊羊们穿着五颜六色的衣服排队买蔡徐坤演唱会的门票。

问题描述

一开始排的队伍为空，依次发生了 $q$ 次以下三种类型的事件：

• 1 c：来了一只穿颜色 $c$ 衣服的羊，排在队伍尾部。
• 2：当前排在队首的羊买到了票（欧耶）并离开队伍，回家睡觉。
• 3 c：刮来一阵大风，把当前队伍中所有穿颜色 $c$ 衣服的羊全都吹走了（从队伍里删除）。

依次对每个第二类事件，输出买到票的羊的衣服颜色。

输入格式

从文件 queue.in 中读取数据。

第一行一个正整数 $q$。

后面 $q$ 行每行一至两个正整数，表示依次发生的各事件，具体格式如题面所述。

输出格式

输出到文件 queue.out。

对每个第二类事件，输出一行一个整数，表示买到票的羊的衣服颜色。特别地，如果当时队伍为空，则对应行输出 -1。

样例 1

8
2
1 1
1 1
1 2
2
1 1
3 1
2

-1
1
2

样例 1 解释

• 2：队伍为空，输出 -1。
• 1 1：队伍为 1。
• 1 1：队伍为 1 1。
• 1 2：队伍为 1 1 2（左侧是队首）。
• 2：输出 1，队伍为 1 2。
• 1 1：队伍为 1 2 1。
• 3 1：队伍为 2（两个 1 都被吹走了）。
• 2：输出 2。

数据规模与约定

• 50% 的数据，$q\leq 100$。
• 另 30% 的数据，没有第三类指令。
• 100% 的数据，$1\leq q\leq 1000000$，$1\leq c\leq 1000000$，保证输入的事件格式符合题面所述。

所有测试点时限均为 1 秒，内存限制均为 512 MiB。

文件读写说明

必须使用文件读写。在 main 函数开头加入：

freopen("queue.in", "r", stdin);
freopen("queue.out", "w", stdout);