问题描述

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

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

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

输入格式

第一行输入一个整数 $Q$，表示查询的总次数。

接下来输入 $Q$ 行，第 $i$ 行表示第 $i$ 个查询，格式为以下三种之一：

• 1 l
• 2
• 3 k

输出格式

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

第 $i$ 行输出第 $i$ 个类型 $3$ 查询对应的答案。

样例输入 1

7
1 5
1 7
3 2
1 3
1 4
2
3 3

样例输出 1

5
10

样例输入 2

3
1 1
2
1 3

样例输出 2

样例输入 3

10
1 15
1 10
1 5
2
1 5
1 10
1 15
2
3 4
3 2

样例输出 3

20
5

说明

样例 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 查询，因此输出为空。

评测数据规模

对于所有评测数据：

• $1 \leq Q \leq 3 \times 10^5$
• 类型 1 查询中：$1 \leq l \leq 10^9$
• 类型 2 查询保证执行时队列非空
• 类型 3 查询中：设当前队列中有 $n$ 条蛇，则 $1 \leq k \leq n$
• 所有输入均为整数