package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
	"strings"
)

var data []byte
var idx int
var seg []int64
var mask int

func nextInt() int {
	n := len(data)
	for idx < n && (data[idx] < '0' || data[idx] > '9') && data[idx] != '-' {
		idx++
	}
	sign := 1
	if data[idx] == '-' {
		sign = -1
		idx++
	}
	val := 0
	for idx < n && data[idx] >= '0' && data[idx] <= '9' {
		val = val*10 + int(data[idx]-'0')
		idx++
	}
	return val * sign
}

func build(node, level, start int, arr []int64) {
	if level == 0 {
		seg[node] = arr[start]
		return
	}
	half := 1 << (level - 1)
	build(node<<1, level-1, start, arr)
	build(node<<1|1, level-1, start+half, arr)
	seg[node] = seg[node<<1] + seg[node<<1|1]
}

func update(node, level, pos int, val int64) {
	if level == 0 {
		seg[node] = val
		return
	}
	half := 1 << (level - 1)
	leftNode, rightNode := node<<1, node<<1|1
	if (mask>>uint(level-1))&1 == 1 {
		leftNode, rightNode = rightNode, leftNode
	}
	if pos < half {
		update(leftNode, level-1, pos, val)
	} else {
		update(rightNode, level-1, pos-half, val)
	}
	seg[node] = seg[node<<1] + seg[node<<1|1]
}

func query(node, level, l, r int) int64 {
	if l == 0 && r == (1<<level)-1 {
		return seg[node]
	}
	if level == 0 {
		return seg[node]
	}
	half := 1 << (level - 1)
	leftNode, rightNode := node<<1, node<<1|1
	if (mask>>uint(level-1))&1 == 1 {
		leftNode, rightNode = rightNode, leftNode
	}
	if r < half {
		return query(leftNode, level-1, l, r)
	}
	if l >= half {
		return query(rightNode, level-1, l-half, r-half)
	}
	return query(leftNode, level-1, l, half-1) + query(rightNode, level-1, 0, r-half)
}

func main() {
	data, _ = io.ReadAll(os.Stdin)
	n := nextInt()
	q := nextInt()
	size := 1 << n
	arr := make([]int64, size)
	for i := 0; i < size; i++ {
		arr[i] = int64(nextInt())
	}
	seg = make([]int64, size*4)
	build(1, n, 0, arr)

	var out strings.Builder
	out.Grow(q * 20)

	for i := 0; i < q; i++ {
		t := nextInt()
		switch t {
		case 1:
			x := nextInt() - 1
			k := int64(nextInt())
			update(1, n, x, k)
		case 2:
			k := nextInt()
			mask ^= (1 << k) - 1
		case 3:
			k := nextInt()
			mask ^= 1 << k
		case 4:
			l := nextInt() - 1
			r := nextInt() - 1
			out.WriteString(strconv.FormatInt(query(1, n, l, r), 10))
			out.WriteByte('\n')
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 1<<20)
	w.WriteString(out.String())
	w.Flush()
}