题目描述

给您一个长度为 $2^n$ 的数组 $a$，您现在需要处理 $q$ 个询问，每个询问是以下 4 种类型之一：

1. $Replace(x, k)$ 把 $a_x$ 修改为 $k$；
2. $Reverse(k)$ 对于每一个 $i(i\ge 1)$ ，把区间 $[(i-1)\cdot 2^k+1, i\cdot 2^k]$ 的元素翻转；
3. $Swap(k)$ 对于每一个 $i(i\ge 1)$ ，交换区间 $[(2i-2)\cdot2^k+1,(2i-1)\cdot2^k]$ 和 $[(2i-1)\cdot2^k+1,2i\cdot2^k]$ 的所有元素；
4. $Sum(l,r)$ 输出区间 $[l,r]$ 中所有元素的和。

您需要写一个能快速处理以上询问的程序。

输入格式

第一行包含两个整数 $n$ 、 $q$ ( $0 \le n \le 18$ ; $1 \le q \le 10^5$ )--数组长度 $a$ 和查询次数。

第二行包含 $2^n$ 个整数 $a_1, a_2, \ldots, a_{2^n}$ ( $0 \le a_i \le 10^9$ )。

接下来的 $q$ 行包含查询，每行一个。每个查询都有 $4$ 种类型：

• 1 x k ( $1 \le x \le 2^n$ ; $0 \le k \le 10^9$ ) - $Replace(x, k)$ ;
• 2 k ( $0 \le k \le n$ ) - $Reverse(k)$ ;
• 3 k ( $0 \le k < n$ ) - $Swap(k)$ ;
• 4 l r ( $1 \le l \le r \le 2^n$ ) - $Sum(l, r)$ .

保证至少有一个 $Sum$ 查询。

输出格式

打印每个 $Sum$ 查询的答案。

2 3
7 4 9 9
1 2 8
3 1
4 2 4

24

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

29
22
1

提示

在第一个示例中，最初数组 $a$ 等于 $\{7,4,9,9\}$ 。

处理第一个查询后，数组 $a$ 变为 $\{7,8,9,9\}$ 。

处理第二个查询后，数组 $a_i$ 变为 $\{9,9,7,8\}$ 。

因此，第三个查询的答案为 $9+7+8=24$ 。

在第二个示例中，最初数组 $a$ 等于 $\{7,0,8,8,7,1,5,2\}$ 。接下来的情况是

1. $Sum(3, 7)$ $\to$ $8 + 8 + 7 + 1 + 5 = 29$ ;
2. $Reverse(1)$ $\to$ $\{0,7,8,8,1,7,2,5\}$ ;
3. $Swap(2)$ $\to$ $\{1,7,2,5,0,7,8,8\}$ ;
4. $Sum(1, 6)$ $\to$ $1 + 7 + 2 + 5 + 0 + 7 = 22$ ;
5. $Reverse(3)$ $\to$ $\{8,8,7,0,5,2,7,1\}$ ;
6. $Replace(5, 16)$ $\to$ $\{8,8,7,0,16,2,7,1\}$ ;
7. $Sum(8, 8)$ $\to$ $1$ ;
8. $Swap(0)$ $\to$ $\{8,8,0,7,2,16,1,7\}$ .