题目描述

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

1. 1 x c: 在圆柱体的右端插入 $c$个球，每个球上写有数字 $x$。
2. 2 c: 取出圆柱体中最左边的 $c$ 个球，并打印取出的球上写的数字之和。

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

输入格式

输入从标准输入中以下列格式给出：

$Q$

${\rm\ query}_1$

$\vdots$

${\rm\ query}_Q$

第 $i$个查询 $query_i$ 是以下两种格式之一。

$1$ $x$ $c$

$2$ $c$

输出格式

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

输入输出样例 #1

输入 #1

4
1 2 3
2 2
1 3 4
2 3

输出 #1

4
8

输入输出样例 #2

输入 #2

2
1 1000000000 1000000000
2 1000000000

输出 #2

1000000000000000000

输入输出样例 #3

输入 #3

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

输出 #3

说明/提示

样例 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$ 个球
• 输入中的所有值都是整数。