多重幻象走廊中的芙莉莲

题目描述

在一次一级魔法师的考试中，芙莉莲身处一条多重幻象的走廊中。她面前是一条由 $n$ 段组成的漫长走廊，编号从 $1$ 到 $n$。第 $i$ 段上有一颗能量为 $a_i$ 的水晶。初始时，所有段都被幻象完全遮蔽。

芙莉莲可以对区间施展显现魔法。但每个魔法并非作用于区间内的所有位置。

当对区间 $[l, r]$ 施展魔法时，会在那些从 $l$ 开始，依次加上步长 $2, 3, 2, 3, \ldots$（循环）直到下标超过 $r$ 的位置上增加一层显现层。也就是说，魔法作用于位置 $[l,\ l+2,\ l+5,\ l+7,\ l+10,\ \ldots]$（所有不超过 $r$ 的此类位置）。每个魔法会在每个这样的位置上恰好增加一层显现层。

不同魔法的层数在同一位置会叠加。如果一个段上至少有一层显现层，则该水晶被认为是“可访问的”。

然而，赞因会介入并取消芙莉莲的魔法。当取消一个施加在 $[l, r]$ 上的魔法时，会在该魔法作用的每个位置上恰好移除一层显现层。保证每次取消操作对应于之前施加且尚未取消的、位于同一区间 $[l, r]$ 的芙莉莲魔法。

需要处理 $q$ 个三种类型的操作：

• + l r —— 芙莉莲对区间 $[l, r]$ 施展一个显现魔法；
• - l r —— 赞因取消一个芙莉莲的处于激活状态的、施加在区间 $[l, r]$ 上的魔法；
• ? l r —— 询问区间 $[l, r]$ 内所有位置上可访问水晶的能量之和。

对于每个第三类操作，输出所求的和。

输入格式

第一行给出两个整数 $n$ 和 $q$ —— 水晶的个数和操作的个数（$1 \le n, q \le 5 \cdot 10^5$）。

第二行给出 $n$ 个整数 $a_1, a_2, \ldots, a_n$ —— 水晶的能量值（$0 \le a_i \le 10^9$）。

接下来 $q$ 行每行描述一个操作，格式如上所述（所有操作保证 $1 \le l \le r \le n$）。

输出格式

对于每个 ? 类型的操作，输出一行一个整数 —— 指定区间内可访问水晶的能量之和。

评分系统

每个子任务的分数仅当通过该子任务的所有测试以及其所依赖子任务的所有测试时才会被获得。

样例

样例 1

输入

3 6
12 20 2
? 2 2
+ 1 2
? 2 2
+ 1 3
? 1 1
- 1 2

输出

0
0
12

样例 2

输入

5 6
9 3 22 37 31
? 1 1
+ 5 5
? 3 4
+ 1 4
? 2 2
- 1 4

输出

0
0
0