AT_abc389_c.[ABC389C] Snake Queue

存在一个蛇的队列。初始时队列为空。

给定 $ Q $ 个查询，请按顺序处理。查询有以下三种类型：

• 类型 1：以 1 l 的形式给出。将长度为 $ l $ 的蛇添加到队列末尾。此时，若原队列为空，则添加的蛇的头部坐标为 $ 0 $；否则，新蛇的头部坐标为队列最后一条蛇的头部坐标加上其长度。
• 类型 2：以 2 的形式给出。队列最前端的蛇离开队列。此时保证队列不为空。设离开的蛇长度为 $ m $，队列中剩余所有蛇的头部坐标将减少 $ m $。
• 类型 3：以 3 k 的形式给出。输出队列中从前往后数第 $ k $ 条蛇的头部坐标。此时保证队列中至少有 $ k $ 条蛇。

输入通过标准输入给出，格式如下：

$ Q $

$ \text{query}_1 $

$ \text{query}_2 $

$ \vdots $

$ \text{query}_Q $

其中，$ \text{query}_i $ 表示第 $ i $ 个查询，为以下形式之一：

$ 1 $ $ l $

$ 2 $

$ 3 $ $ k $

设类型 3 的查询共有 $ q $ 个，输出 $ q $ 行。第 $ i $ 行输出第 $ i $ 个类型 3 查询的答案。

约束条件

• $ 1 \leq Q \leq 3 \times 10^{5} $
• 类型 1 的查询中，$ 1 \leq l \leq 10^{9} $
• 类型 2 的查询保证队列不为空
• 类型 3 的查询中，设队列中有 $ n $ 条蛇，则 $ 1 \leq k \leq n $
• 输入均为整数

样例解释 1

• 第 1 个查询：添加长度为 $ 5 $ 的蛇。队列为空，因此其头部坐标为 $ 0 $。
• 第 2 个查询：添加长度为 $ 7 $ 的蛇。原最后一条蛇的头部坐标为 $ 0 $ 且长度为 $ 5 $，因此新蛇的头部坐标为 $ 5 $。
• 第 3 个查询：输出第 2 条蛇的头部坐标。队列中蛇的头部坐标依次为 $ 0, 5 $，因此输出 5。
• 第 4 个查询：添加长度为 $ 3 $ 的蛇。原最后一条蛇的头部坐标为 $ 5 $ 且长度为 $ 7 $，因此新蛇的头部坐标为 $ 12 $。
• 第 5 个查询：添加长度为 $ 4 $ 的蛇。原最后一条蛇的头部坐标为 $ 12 $ 且长度为 $ 3 $，因此新蛇的头部坐标为 $ 15 $。
• 第 6 个查询：移除队列最前端的蛇（长度为 $ 5 $）。剩余蛇的头部坐标减少 $ 5 $，此时坐标为 $ 0, 7, 10 $。
• 第 7 个查询：输出第 3 条蛇的头部坐标。队列中蛇的头部坐标依次为 $ 0, 7, 10 $，因此输出 10。

样例解释 2

可能存在没有类型 3 查询的情况。

翻译由 DeepSeek R1 完成