#P18218. The Tower
The Tower
The Tower
蓬莱山辉夜最近经常在名为 Mikufans 的视频分享平台上看视频。平台允许用户发送弹幕,有时屏幕上会同时出现很多条消息。

原图来源:原题引用的视频。
为简化问题,我们只考虑顶部弹幕:每条顶部弹幕恰好占据一行。行从上到下依次编号为 ,总行数没有上限。屏幕只能显示前 行,但溢出屏幕的弹幕仍然存在,并按同样的规则维护。
开始时所有行都是空的。视频播放期间依次发生以下三种事件:
- 一个新用户发送 条顶部弹幕。这些消息占据当前从上往下最靠前的 个空行。新用户的 ID 为此前从未使用过的最小正整数,也就是按照新用户出现顺序依次编号为 。
- 某个用户发送的所有弹幕消失,对应的行变为空行。其他消息仍然留在原来的行,不会上移或下移。已经使用过的用户 ID 不会重新分配。
- 查询第 行当前的消息来自哪个用户。如果该行为空,则答案为 。
请按事件发生顺序处理所有查询。
输入格式
第一行包含一个整数 ,表示事件数。
接下来 行,每行描述一个事件:
1 k:一个新用户发送 条顶部弹幕;2 u:用户 的所有消息消失。保证用户 已经出现,且其消息此前尚未消失;3 l:查询第 行。
输出格式
对于每个类型为 3 的事件,输出一行一个整数,表示该行的发送用户 ID;若该行为空则输出 。
如果没有类型为 3 的事件,则无需输出任何内容。
数据范围
- ;
- 对于类型为
1的事件,; - 对于类型为
3的事件,; - 所有类型为
2的事件都满足输入格式中给出的有效性保证。
样例 1
7
1 2
1 4
3 3
2 1
3 2
1 4
3 7
2
0
3
样例 2
5
3 6
3 8
1 2
1 5
3 2
0
0
1