#P18218. The Tower

The Tower

The Tower

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

原题弹幕画面

原图来源:原题引用的视频。

为简化问题,我们只考虑顶部弹幕:每条顶部弹幕恰好占据一行。行从上到下依次编号为 1,2,3,…1,2,3,\ldots,总行数没有上限。屏幕只能显示前 10910^9 行,但溢出屏幕的弹幕仍然存在,并按同样的规则维护。

开始时所有行都是空的。视频播放期间依次发生以下三种事件:

  1. 一个新用户发送 kk 条顶部弹幕。这些消息占据当前从上往下最靠前的 kk 个空行。新用户的 ID 为此前从未使用过的最小正整数,也就是按照新用户出现顺序依次编号为 1,2,3,…1,2,3,\ldots。
  2. 某个用户发送的所有弹幕消失,对应的行变为空行。其他消息仍然留在原来的行,不会上移或下移。已经使用过的用户 ID 不会重新分配。
  3. 查询第 ll 行当前的消息来自哪个用户。如果该行为空,则答案为 00。

请按事件发生顺序处理所有查询。

输入格式

第一行包含一个整数 nn,表示事件数。

接下来 nn 行,每行描述一个事件:

  • 1 k:一个新用户发送 kk 条顶部弹幕;
  • 2 u:用户 uu 的所有消息消失。保证用户 uu 已经出现,且其消息此前尚未消失;
  • 3 l:查询第 ll 行。

输出格式

对于每个类型为 3 的事件,输出一行一个整数,表示该行的发送用户 ID;若该行为空则输出 00。

如果没有类型为 3 的事件,则无需输出任何内容。

数据范围

  • 1≤n≤5×1051\le n\le5\times10^5;
  • 对于类型为 1 的事件,1≤k≤1091\le k\le10^9;
  • 对于类型为 3 的事件,1≤l≤1091\le l\le10^9;
  • 所有类型为 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