给你一个长度为$$$2^n$$$的数组$$$a$$$。您应该处理对其的 $$$q$$$ 查询。每个查询都有以下 $$$4$$$ 类型之一:
1. $$$Replace(x, k)$$$ — 将 $$$a_x$$$ 更改为 $$$k$$$;
2. $$$Reverse(k)$$$ — 对所有 $$$i$$$ 反转每个子数组 $$$[(i-1) \cdot 2^k+1, i \cdot 2^k]$$$ ($$$i \ge 1$$$);
3. $$$Swap(k)$$$ — 交换子数组 $$$[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$$$ 和 $$$[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$$$ 对于所有 $$$i$$$ ($$$i \ge 1$$$);
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$$$) — $$$替换(x, k)$$$;
- "$$$2$$$ $$$k$$$" ($$$0 \le k \le n$$$) — $$$反向(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$$$ 查询的答案。
示例
输入 #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
注意
在第一个示例中,最初,数组 $$$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. $$$反向(1)$$$ $$$\到$$$ $$$\{0,7,8,8,1,7,2,5\}$$$;
3. $$$交换(2)$$$ $$$\至$$$ $$$\{1,7,2,5,0,7,8,8\}$$$;
4. $$$Sum(1, 6)$$$ $$$\to$$$ $$$1 + 7 + 2 + 5 + 0 + 7 = 22$$$;
5. $$$反向(3)$$$ $$$\到$$$ $$$\{8,8,7,0,5,2,7,1\}$$$;
6. $$$替换(5, 16)$$$ $$$\to$$$ $$$\{8,8,7,0,16,2,7,1\}$$$;
7. $$$Sum(8, 8)$$$ $$$\to$$$ $$$1$$$;
8. $$$交换(0)$$$ $$$\至$$$ $$$\{8,8,0,7,2,16,1,7\}$$$。