该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

区间乐趣

题目描述

徐老师正在实现一个简化版的数据结构。
他维护一个初始为空的整数数组 A，并且只允许在数组末尾进行修改：

• 有时徐老师会在末尾追加一个整数（相当于 push）
• 有时徐老师会删除末尾的一个元素（相当于 pop）
• 同时，徐老师还想随时查询当前数组中某个区间 $[L, R]$ 的元素和

现在，徐老师把这份工作交给你：你需要按顺序处理 $Q$ 次操作，并对每次查询输出答案。

输入格式

第一行输入一个整数 $Q$（$1 \le Q \le 10^6$），表示操作次数。

接下来 $Q$ 行，每行表示一个操作，操作类型如下：

1. 1 x：徐老师在数组末尾追加一个整数 $x$（$1 \le x \le 10^9$）
2. 2 L R：徐老师询问当前数组下标从 $L$ 到 $R$（下标从 $1$ 开始）的元素和
3. 3：徐老师删除当前数组末尾的一个元素

数据保证所有操作合法，具体而言：

• 执行删除操作时，数组一定非空
• 执行查询操作时，$1 \le L \le R \le \text{当前数组长度}$

输出格式

对于每个 2 L R 操作，输出一行一个整数，表示区间 $[L, R]$ 的元素和。

输入输出样例 #1

输入 #1

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

输出 #1

5
6

说明/提示

• 徐老师先依次追加 $2, 3$，此时数组为 $[2, 3]$，查询 $[1,2]$ 得到 $5$
• 随后删除末尾元素 $3$，数组变为 $[2]$；再追加 $4$，数组变为 $[2, 4]$，查询 $[1,2]$ 得到 $6$