题目描述

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

1. 1 x c: 在圆柱体的右端插入$c$个球，每个球上写有数字$x$。

2. 2 c: 取出圆柱体中最左边的$c$个球，并打印取出的球上写的数字之和。
   我们假设球在圆柱体中永远不会改变顺序。

输入格式

输入从标准输入中以下列格式给出：
$Q$
$query_1$
$\vdots$
$query_Q$
第$i$个查询$query_i$是以下两种格式之一。
$1\ x\ c$
$2\ c$

输出格式

按给定顺序输出对类型为2 c的查询的响应，每个响应之间用换行符分隔。

样例

4
1 2 3
2 2
1 3 4
2 3

4
8

2
1 1000000000 1000000000
2 1000000000

1000000000000000000

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

1

样例解释

【样例1说明】

1. 第1个查询，在圆筒右侧插入3个写有数字2的球。圆筒中的球从左到右写有的数字为(2,2,2)。

2. 第2个查询，从圆筒左侧取出2个球。取出的球上写有的数字分别为2,2，总和为4，因此输出4。圆筒中的球从左到右写有的数字变为(2)。

3. 第3个查询，在圆筒右侧插入4个写有数字3的球。圆筒中的球从左到右写有的数字为(2,3,3,3,3)。

4. 第4个查询，从圆筒左侧取出3个球。取出的球上写有的数字分别为2,3,3，总和为8，因此输出8。圆筒中的球从左到右写有的数字变为(3,3)。

【样例3说明】
可能不需要做任何输出。

数据范围

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

来源

• AtCoder ABC247D