序列变换（runes）

题目描述

Y 同学在探索遗迹时发现了一行共 $2^n$ 个神秘的符文，每个符文都蕴含着一定的能量值。我们将这些符文从左到右依次编号为 $1, 2, \dots, 2^n$，第 $i$ 个符文的初始能量值为 $a_i$。

这行符文的结构具有特殊的分治特性，Y 同学可以通过施加咒语来改变符文的排列或能量分布。总共有 $q$ 次操作，操作分为以下四类：

1. 能量强化：给定位置 $x$ 和能量值 $k$，将第 $x$ 个符文的能量值修改为 $k$。
2. 镜像翻转：给定参数 $k$，将整个符文序列划分为 $2^{n-k}$ 个连续的子块，每个子块的长度均为 $2^k$。对于每一个子块，将其内部的符文顺序进行完全反转。
3. 结构互换：给定参数 $k$，将整个符文序列划分为 $2^{n-k-1}$ 个连续的子块，每个子块的长度均为 $2^{k+1}$。对于每一个子块，交换其左半部分（长度为 $2^k$）与右半部分（长度为 $2^k$）的符文位置。
4. 能量感应：给定闭区间 $[l, r]$，计算并输出该区间内所有符文能量值的总和。

请你帮助 Y 同学计算出每次“能量感应”操作的结果。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示序列长度的对数和操作的总次数。

第二行包含 $2^n$ 个整数 $a_1, a_2, \dots, a_{2^n}$，表示各个符文的初始能量值。

接下来的 $q$ 行，每行描述一个操作：

• 1 x k：执行第 1 类操作，将 $a_x$ 修改为 $k$。
• 2 k：执行第 2 类操作，参数为 $k$。
• 3 k：执行第 3 类操作，参数为 $k$。
• 4 l r：执行第 4 类操作，查询区间 $[l, r]$ 的能量总和。

输出格式

对于每个第 4 类操作，输出一行一个整数，代表查询的区间能量总和。

样例

样例输入 #1

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

样例输出 #1

24

样例输入 #2

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

样例输出 #2

29
22
1

数据范围与约定

对于 $100\%$ 的数据，保证 $0 \le n \le 18$，$1 \le q \le 10^5$，$0 \le a_i, k \le 10^9$。 操作参数满足 $1 \le x \le 2^n$，$0 \le k \le n$（第 2 类），$0 \le k < n$（第 3 类），$1 \le l \le r \le 2^n$。

测试点编号	分值	$n \le$	$q \le$	特殊性质
$1 \sim 4$	$20$	$10$	$1000$	无
$5 \sim 8$		$18$	$10^5$	特殊性质 A
$9 \sim 12$				特殊性质 B
$13 \sim 16$		$16$	$5 \cdot 10^4$	无
$17 \sim 20$		$18$	$10^5$

• 特殊性质 A：保证不存在第 2 类（镜像翻转）和第 3 类（结构互换）操作。
• 特殊性质 B：保证不存在第 1 类（能量强化）操作。