题目描述

给定一个初始时长度为 $n$ 的数列 $a$，接下来有 $q$ 次操作，操作分为如下三种类型：

1. $1\ l\ r$：翻转下标区间 $[l, r]$ 范围内的所有元素；
2. $2\ l\ r$：查询下标区间 $[l, r]$ 范围内的所有元素之和；
3. $3\ x$：在数列的末尾插入一个数值为 $x$ 的元素。

对于每次查询操作，你需要输出对应的结果。

输入格式

第一行，两个整数 $n$ 和 $q$，以空格分隔（$1 \le n,q \le 2 \times 10^5$）。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$，两两之间以一个空格分隔（$1 \le a_i \le 1000$）。

接下来 $q$ 行，每行包含一个操作（$1 \le l \le r \le$ 当前数列长度，$1 \le x \le 1000$）。

输出格式

对于每次查询操作（$2\ l\ r$），输出一行包含一个整数，表示下标区间 $[l, r]$ 范围内的所有元素之和，即 $\sum\limits_{i=l}^r a_i$ 。

样例

6 7
1 2 3 4 5 6
2 1 3
1 3 5
2 1 3
3 7
3 8
1 5 8
2 3 7

6
8
30

说明/提示

样例解释

• 初始时，数列 $a = \{ 1, 2, 3, 4, 5, 6 \}$
• 第 $1$ 次操作查询下标区间 $[1, 3]$ 的元素和为 $1 + 2 + 3 = 6$
• 第 $2$ 次操作翻转下标区间 $[3, 5]$ 后数列变为 $a = \{ 1, 2, 5, 4, 3, 6 \}$
• 第 $3$ 次操作查询下标区间 $[1, 3]$ 的元素和为 $1 + 2 + 5 = 8$
• 第 $4$ 次操作在数列末尾添加 $7$ 后，数列变为 $a = \{ 1, 2, 5, 4, 3, 6, 7 \}$
• 第 $5$ 次操作在数列末尾添加 $8$ 后，数列变为 $a = \{ 1, 2, 5, 4, 3, 6, 7, 8 \}$
• 第 $6$ 次操作翻转下标区间 $[5, 8]$ 后数列变为 $a = \{ 1, 2, 5, 4, 8, 7, 6, 3 \}$
• 第 $7$ 次操作查询下标区间 $[3, 7]$ 的元素和为 $5+4+8+7+6 = 30$

数据规模与约定

• 对于 $30\%$ 的数据，$n,q \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,q \le 2 \times 10^5; 1 \le a_i, x \le 1000$