问题描述

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

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

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

输入

输入格式如下：

Q
query1
query2
...
queryQ

每个查询 queryi 是以下两种格式之一：

• 1 x c：表示插入 c 个数字为 x 的球。
• 2 c：表示取出 c 个最左边的球，并计算它们的和。

输出

对于每个 2 c 类型的查询，输出这些球的数字之和，并在每个输出结果之间换行。

限制

• 1 ≤ Q ≤ 2 × 10^5
• 0 ≤ x ≤ 10^9
• 1 ≤ c ≤ 10^9
• 每当有类型为 2 c 的查询时，圆柱体中至少有 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，输出4。
• 第3个查询：插入4个数字为3的球，圆柱体现在有（2, 3, 3, 3, 3）这五个球。
• 第4个查询：取出圆柱体中最左边的3个球，取出的球是（2, 3, 3），它们的和为8，输出8。

样例输入 2

2
1 1000000000 1000000000
2 1000000000

样例输出 2

1000000000000000000

​解释​：

• 第1个查询：插入1000000000个数字为1000000000的球，圆柱体现在有1000000000个数字为1000000000的球。
• 第2个查询：取出1000000000个最左边的球，取出的球是（1000000000，1000000000，...），它们的和是 1000000000 * 1000000000，输出 1000000000000000000。

样例输入 3

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

样例输出 3

（没有输出）

​解释​：

• 所有的查询都是插入球的操作，且没有任何 2 c 类型的查询，因此没有输出。

解题思路

这个问题可以使用队列（Queue）来模拟。对于每个查询：

1. ​**类型 1 x c**​：将 c 个数字为 x 的球插入到队列的末尾。
2. ​**类型 2 c**​：从队列的前面取出 c 个球，并计算它们的和。

因为输入的 Q 查询数量最大为 2 * 10^5，所以我们需要确保每个操作的时间复杂度尽可能低。队列（deque）适合用来执行这种插入和删除操作，因为其时间复杂度是常数级别的。