问题描述

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \ldots, A_N)$。

按顺序处理 $Q$ 个查询，类型有两种：

• 1 c：将序列 $A$ 的第一个元素移到末尾，重复 $c$ 次。
• 2 l r：输出 $\sum_{i=l}^{r} A_i$ 的值。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

接下来 $Q$ 行，每行一个查询（1 c 或 2 l r）。

输出格式

对于每个 2 l r 查询，输出一行一个整数。

样例输入 1

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

样例输出 1

8
9

样例输入 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

样例输出 2

31
31
7
4

评测数据规模

对于所有数据，保证 $1 \le N \le 2 \times 10^5$，$1 \le Q \le 2 \times 10^5$，$1 \le A_i \le 10^9$，$1 \le c \le N$，$1 \le l \le r \le N$。至少存在一次类型 $2$ 的查询。