问题描述

有一个初始为空的整数序列 $A = ()$。现在有 $Q$ 个操作，请按给定顺序依次处理。操作有以下两种类型：

• 类型 1：以 1 c x 的形式给出。向序列 $A$ 的末尾添加 $c$ 个整数 $x$。
• 类型 2：以 2 k 的形式给出。删除序列 $A$ 的前 $k$ 个元素，并输出被删除的 $k$ 个整数的总和（保证此时 $k$ 不超过当前序列 $A$ 的长度）。

输入格式

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

接下来输入 $Q$ 行，第 $i$ 行表示第 $i$ 个操作，格式为以下两种之一：

• 1 c x
• 2 k

输出格式

设类型 $2$ 的操作共有 $q$ 个，输出共 $q$ 行。

第 $i$ 行输出第 $i$ 个类型 $2$ 操作计算得到的总和。

样例输入 1

5
1 2 3
1 4 5
2 3
1 6 2
2 5

样例输出 1

11
19

样例输入 2

10
1 75 22
1 81 72
1 2 97
1 84 82
1 2 32
1 39 57
2 45
1 40 16
2 32
2 42

样例输出 2

990
804
3024

样例输入 3

10
1 160449218 954291757
2 17217760
1 353195922 501899080
1 350034067 910748511
1 824284691 470338674
2 180999835
1 131381221 677959980
1 346948152 208032501
1 893229302 506147731
2 298309896

样例输出 3

16430766442004320
155640513381884866
149721462357295680

说明

样例 1 解释：

• 第 1 个操作：向序列 $A$ 末尾添加 $2$ 个 $3$，此时 $A = (3, 3)$。
• 第 2 个操作：向序列 $A$ 末尾添加 $4$ 个 $5$，此时 $A = (3, 3, 5, 5, 5, 5)$。
• 第 3 个操作：删除序列 $A$ 的前 $3$ 个元素，被删除元素的总和为 $3 + 3 + 5 = 11$，输出 11；删除后序列变为 $A = (5, 5, 5)$。
• 第 4 个操作：向序列 $A$ 末尾添加 $6$ 个 $2$，此时 $A = (5, 5, 5, 2, 2, 2, 2, 2, 2)$。
• 第 5 个操作：删除序列 $A$ 的前 $5$ 个元素，被删除元素的总和为 $5 + 5 + 5 + 2 + 2 = 19$，输出 19；删除后序列变为 $A = (2, 2, 2, 2)$。

评测数据规模

对于所有评测数据：

• $1 \leq Q \leq 2 \times 10^5$
• 类型 1 操作中：$1 \leq c \leq 10^9$，$1 \leq x \leq 10^9$
• 类型 2 操作中：设此时序列 $A$ 的长度为 $n$，则 $1 \leq k \leq \min(10^9, n)$
• 所有输入均为整数