You are given an array $a$ of length $2^n$. You should process $q$ queries on it. Each query has one of the following $4$ types:   $Replace(x, k)$ — change $a_x$ to $k$;  $Reverse(k)$ — reverse each subarray $[(i-1) \cdot 2^k+1, i \cdot 2^k]$ for all $i$ ($i \ge 1$);  $Swap(k)$ — swap subarrays $[(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k]$ and $[(2i-1) \cdot 2^k+1, 2i \cdot 2^k]$ for all $i$ ($i \ge 1$);  $Sum(l, r)$ — print the sum of the elements of subarray $[l, r]$. 

Write a program that can quickly process given queries.


-----Input-----

The first line contains two integers $n$, $q$ ($0 \le n \le 18$; $1 \le q \le 10^5$) — the length of array $a$ and the number of queries.

The second line contains $2^n$ integers $a_1, a_2, \ldots, a_{2^n}$ ($0 \le a_i \le 10^9$).

Next $q$ lines contains queries — one per line. Each query has one of $4$ types:   "$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)$. 

It is guaranteed that there is at least one $Sum$ query.


-----Output-----

Print the answer for each $Sum$ query.


-----Examples-----
Input
2 3
7 4 9 9
1 2 8
3 1
4 2 4

Output
24

Input
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

Output
29
22
1



-----Note-----

In the first sample, initially, the array $a$ is equal to $\{7,4,9,9\}$.

After processing the first query. the array $a$ becomes $\{7,8,9,9\}$.

After processing the second query, the array $a_i$ becomes $\{9,9,7,8\}$

Therefore, the answer to the third query is $9+7+8=24$.

In the second sample, initially, the array $a$ is equal to $\{7,0,8,8,7,1,5,2\}$. What happens next is:   $Sum(3, 7)$ $\to$ $8 + 8 + 7 + 1 + 5 = 29$;  $Reverse(1)$ $\to$ $\{0,7,8,8,1,7,2,5\}$;  $Swap(2)$ $\to$ $\{1,7,2,5,0,7,8,8\}$;  $Sum(1, 6)$ $\to$ $1 + 7 + 2 + 5 + 0 + 7 = 22$;  $Reverse(3)$ $\to$ $\{8,8,7,0,5,2,7,1\}$;  $Replace(5, 16)$ $\to$ $\{8,8,7,0,16,2,7,1\}$;  $Sum(8, 8)$ $\to$ $1$;  $Swap(0)$ $\to$ $\{8,8,0,7,2,16,1,7\}$.

Difficulty: MEDIUM

Starter code:

Solutions:
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, q) = map(int, input().split())
QueryList = [0] * n
SegmentTree = []
a = list(map(int, input().split()))
for i in range(n + 1):
	SegmentTree.append([0] * (1 << n - i))
for i in range(1 << n):
	for j in range(n + 1):
		SegmentTree[j][i >> j] += a[i]

def FindSum(m):
	summ = 0
	for i in range(n + 1):
		if m & 1 << i:
			m -= 1 << i
			mCpy = m
			for j in range(i, n):
				if QueryList[j]:
					mCpy ^= (1 << j + 1) - (1 << i)
			summ += SegmentTree[i][mCpy >> i]
	return summ
for _ in range(q):
	t = list(map(int, input().split()))
	if t[0] == 1:
		loc = t[1] - 1
		for i in range(n):
			if QueryList[i]:
				loc ^= (1 << i + 1) - 1
		increment = t[2] - SegmentTree[0][loc]
		for j in range(n + 1):
			SegmentTree[j][loc >> j] += increment
	if t[0] == 2:
		if t[1] == 0:
			continue
		QueryList[t[1] - 1] = 1 - QueryList[t[1] - 1]
	if t[0] == 3:
		QueryList[t[1]] = 1 - QueryList[t[1]]
		if t[1] == 0:
			continue
		QueryList[t[1] - 1] = 1 - QueryList[t[1] - 1]
	if t[0] == 4:
		print(FindSum(t[2]) - FindSum(t[1] - 1))


from sys import stdin
REPLACE_ID = 1
REVERSE_ID = 2
SWAP_ID = 3
SUM_ID = 4

def main():
	(n, q) = _read_ints()
	a = tuple(_read_ints())
	requests = tuple((_read_ints() for _ in range(q)))
	for result in compute_requests_results(a, requests):
		print(result)

def _read_ints():
	return map(int, stdin.readline().split(' '))

def compute_requests_results(initial_array, requests):
	tree = _Tree(initial_array)
	for (request_id, *request_args) in requests:
		if request_id == REPLACE_ID:
			(index, new_value) = request_args
			tree[index - 1] = new_value
		elif request_id == REVERSE_ID:
			(k,) = request_args
			tree.reverse(k)
		elif request_id == SWAP_ID:
			(k,) = request_args
			tree.swap(k)
		else:
			assert request_id == SUM_ID
			(l, r) = request_args
			yield tree.find_sum(l - 1, r - 1)

class _Tree:

	def __init__(self, array):
		array = list(array)
		self._levels = [array]
		self._levels_sizes = [len(array)]
		self._nodes_sizes = [1]
		while self._levels_sizes[-1] > 1:
			last_size = self._levels_sizes[-1]
			last_level = self._levels[-1]
			last_node_size = self._nodes_sizes[-1]
			new_size = last_size // 2
			new_level = [last_level[2 * i] + last_level[2 * i + 1] for i in range(new_size)]
			new_node_size = last_node_size * 2
			self._levels_sizes.append(new_size)
			self._levels.append(new_level)
			self._nodes_sizes.append(new_node_size)
		self._levels = tuple(self._levels)
		self._is_swapped = [False for level in self._levels]

	def __getitem__(self, index):
		i_curr_level = len(self._levels) - 1
		curr_node_index = 0
		while i_curr_level > 0:
			i_new_level = i_curr_level - 1
			new_node_size = self._nodes_sizes[i_new_level]
			is_right = 1 if index >= new_node_size else 0
			is_right = is_right if not self._is_swapped[i_curr_level] else 1 - is_right
			new_node_index = curr_node_index * 2 + is_right
			i_curr_level = i_new_level
			index %= new_node_size
			curr_node_index = new_node_index
		return self._levels[i_curr_level][curr_node_index]

	def __setitem__(self, index, value):
		old_value = self[index]
		delta = value - old_value
		i_curr_level = len(self._levels) - 1
		curr_node_index = 0
		while i_curr_level > 0:
			self._levels[i_curr_level][curr_node_index] += delta
			i_new_level = i_curr_level - 1
			new_node_size = self._nodes_sizes[i_new_level]
			is_right = 1 if index >= new_node_size else 0
			is_right = is_right if not self._is_swapped[i_curr_level] else 1 - is_right
			new_node_index = curr_node_index * 2 + is_right
			i_curr_level = i_new_level
			index %= new_node_size
			curr_node_index = new_node_index
		self._levels[i_curr_level][curr_node_index] += delta

	def find_sum(self, l, r):
		return self._find_sum_before(r + 1) - self._find_sum_before(l)

	def _find_sum_before(self, index):
		if index == len(self._levels[0]):
			return self._levels[-1][0]
		result_sum = 0
		i_curr_level = len(self._levels) - 1
		curr_node_index = 0
		while i_curr_level > 0:
			i_new_level = i_curr_level - 1
			new_node_size = self._nodes_sizes[i_new_level]
			is_right = 1 if index >= new_node_size else 0
			is_swapped = self._is_swapped[i_curr_level]
			new_node_index = curr_node_index * 2 + (is_right if not is_swapped else 1 - is_right)
			denied_node_index = curr_node_index * 2 + (is_right if is_swapped else 1 - is_right)
			if is_right:
				result_sum += self._levels[i_new_level][denied_node_index]
			i_curr_level = i_new_level
			index %= new_node_size
			curr_node_index = new_node_index
		return result_sum

	def swap(self, k):
		self._is_swapped[k + 1] = not self._is_swapped[k + 1]

	def reverse(self, k):
		for i in range(k):
			self.swap(i)
main()


class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
bit = BIT(2 ** n)
for i in range(2 ** n):
	bit.update(i + 1, a[i])
b = 0

def Sum(r, xor):
	id = xor
	res = 0
	if r == -1:
		return res
	for i in range(n, -1, -1):
		if r >> i & 1:
			L = id >> i << i
			R = L + (1 << i) - 1
			res += bit.query(R + 1) - bit.query(L)
			id ^= 1 << i
	return res
for _ in range(q):
	query = tuple(map(int, input().split()))
	if query[0] == 1:
		(g, x, k) = query
		x -= 1
		x ^= b
		bit.update(x + 1, k - a[x])
		a[x] = k
	elif query[0] == 2:
		k = query[1]
		b ^= 2 ** k - 1
	elif query[0] == 3:
		k = query[1]
		if k != n:
			b ^= 2 ** k
	else:
		(gl, l, r) = query
		l -= 1
		test = Sum(r, b) - Sum(l, b)
		print(test)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def init():
	for u in range(m - 1, 0, -1):
		tree[u] = tree[u * 2] + tree[u * 2 + 1]

def update(i, a):
	u = (i ^ rev) + m
	tree[u] = a
	while u > 1:
		u >>= 1
		tree[u] = tree[u * 2] + tree[u * 2 + 1]

def sumlr(l, r):
	stack = [(0, m, 1, n - 1)]
	res = 0
	while stack:
		(sl, sr, u, f) = stack.pop()
		if r <= sl or sr <= l:
			continue
		elif l <= sl and sr <= r:
			res += tree[u]
		else:
			sm = (sl + sr) // 2
			stack.append((sl, sm, u * 2 + (rev >> f & 1), f - 1))
			stack.append((sm, sr, u * 2 + 1 - (rev >> f & 1), f - 1))
	return res
(n, q) = MI()
m = 2 ** n
tree = [0] * m + LI()
rev = 0
init()
for _ in range(q):
	t = LI()
	if t[0] == 1:
		(x, k) = t[1:3]
		update(x - 1, k)
	elif t[0] == 2:
		k = t[1]
		rev ^= (1 << k) - 1
	elif t[0] == 3:
		k = t[1]
		rev ^= 1 << k
	else:
		(l, r) = t[1:3]
		print(sumlr(l - 1, r))


class SegTree:

	def __init__(self, init_val, n, ide_ele, seg_func):
		self.segfunc = seg_func
		self.num = 2 ** (n - 1).bit_length()
		self.ide_ele = ide_ele
		self.seg = [self.ide_ele] * 2 * self.num
		for i in range(n):
			self.seg[i + self.num - 1] = init_val[i]
		for i in range(self.num - 2, -1, -1):
			self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

	def update(self, k, x):
		k += self.num - 1
		self.seg[k] = x
		while k + 1:
			k = (k - 1) // 2
			self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

	def query(self, p, q):
		if q <= p:
			return self.ide_ele
		p += self.num - 1
		q += self.num - 2
		res = self.ide_ele
		while q - p > 1:
			if p & 1 == 0:
				res = self.segfunc(res, self.seg[p])
			if q & 1 == 1:
				res = self.segfunc(res, self.seg[q])
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res = self.segfunc(res, self.seg[p])
		else:
			res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
		return res

	def range(self, p, q):
		p += self.num - 1
		q += self.num - 2
		res = []
		while q - p > 1:
			if p & 1 == 0:
				res.append(p)
			if q & 1 == 1:
				res.append(q)
				q -= 1
			p = p // 2
			q = (q - 1) // 2
		if p == q:
			res.append(p)
		else:
			res.append(p)
			res.append(q)
		return res
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
X = list(map(int, input().split()))
ss = SegTree(X, 2 ** N, 0, lambda x, y: x + y)
x = 0
for _ in range(Q):
	t = list(map(int, input().split()))
	if t[0] == 1:
		ss.update(t[1] - 1 ^ x, t[2])
	elif t[0] == 2:
		x = x ^ 2 ** t[1] - 1
	elif t[0] == 3:
		x = x ^ 2 ** t[1]
	else:
		rr = ss.range(t[1] - 1, t[2])
		R = 0
		for r in rr:
			rt = r
			c = 0
			while rt:
				rt = (rt - 1) // 2
				c += 1
			ll = N - c
			rk = r - ((1 << c) - 1)
			m = x & ~((1 << ll) - 1)
			m = m >> ll
			R += ss.seg[(rk ^ m) + ((1 << c) - 1)]
		print(R)