题目描述

我们有一个水平圆柱体。给定 $Q$ 个查询，并按照给定的顺序进行处理。
每个查询属于以下两种类型之一。

• 1 x c：将 $c$ 个球插入到圆柱体的右端，每个球上都写着数字 $x$。
• 2 c：取出圆柱体中左侧的 $c$ 个球，并打印被取出的球上的数字之和。

我们假设球在圆柱体内部永远不会改变顺序。

约束条件

• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x \leq 10^9$
• $1 \leq c \leq 10^9$
• 当给出类型为 2 c 的查询时，圆柱体中至少有 $c$ 个球。
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入获得：

$Q$ $查询_1$ $\vdots$ $查询_Q$

第 $i$ 个查询 $查询_i$ 符合以下两种格式中的一种。

$1$ $x$ $c$ $2$ $c$

输出

按照给定顺序打印类型为 2 c 的查询的响应，相邻之间用换行符分隔。

示例输入 1

4
1 2 3
2 2
1 3 4
2 3

示例输出 1

4
8

• 对于第 $1$ 个查询，将 $3$ 个球插入到圆柱体的右端，每个球上写着数字 $2$。
  现在圆柱体中的球从左到右依次为 $(2,2,2)$。
• 对于第 $2$ 个查询，取出圆柱体中左侧的 $2$ 个球。
  被取出的球上的数字是 $2,2$，和为 $4$，应该打印出来。现在圆柱体中只剩下一个球，上面写着数字 $(2)$。
• 对于第 $3$ 个查询，将 $4$ 个球插入到圆柱体的右端，每个球上写着数字 $3$。
  现在圆柱体中的球从左到右依次为 $(2,3,3,3,3)$。
• 对于第 $4$ 个查询，取出圆柱体中左侧的 $3$ 个球。
  被取出的球上的数字是 $2,3,3$，和为 $8$，应该打印出来。现在圆柱体中的球从左到右依次为 $(3,3)$。

示例输入 2

2
1 1000000000 1000000000
2 1000000000

示例输出 2

1000000000000000000

示例输入 3

5
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

示例输出 3

可能不需要打印任何内容。