#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char c = 0;
  int x = 0;
  bool f = 0;
  while (!isdigit(c)) f = c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
  return f ? -x : x;
}
const int N = (1 << 18) + 100;
int a[N], n, q;
struct Segment_tree {
  int rev[N << 2];
  long long sum[N << 2];
  inline void pushup(int o) { sum[o] = sum[o << 1] + sum[o << 1 | 1]; }
  void build(int o, int l, int r) {
    if (l == r) {
      sum[o] = a[l];
      return;
    }
    register int mid = (l + r) >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    pushup(o);
    return;
  }
  void update(int o, int l, int r, int dep, int p, int v) {
    if (l == r) {
      sum[o] = v;
      return;
    }
    register int mid = (l + r) >> 1;
    if (p <= mid)
      update((o << 1) | rev[dep], l, mid, dep - 1, p, v);
    else
      update(((o << 1) | rev[dep]) ^ 1, mid + 1, r, dep - 1, p, v);
    pushup(o);
    return;
  }
  long long query(int o, int l, int r, int dep, int p, int q) {
    if (p <= l && r <= q) return sum[o];
    register int mid = (l + r) >> 1;
    long long ans = 0;
    if (p <= mid) ans += query((o << 1) | rev[dep], l, mid, dep - 1, p, q);
    if (mid < q)
      ans += query(((o << 1) | rev[dep]) ^ 1, mid + 1, r, dep - 1, p, q);
    return ans;
  }
  inline void Reverse(int k) {
    for (int i = 0; i <= k; i++) rev[i] ^= 1;
  }
} T;
int main() {
  n = read();
  q = read();
  for (int i = 1; i <= (1 << n); i++) a[i] = read();
  T.build(1, 1, 1 << n);
  for (int t = 1, opt, l, r; t <= q; t++) {
    opt = read();
    if (opt == 1) {
      l = read();
      r = read();
      T.update(1, 1, 1 << n, n, l, r);
    } else if (opt == 2) {
      l = read();
      T.Reverse(l);
    } else if (opt == 3) {
      l = read();
      T.rev[l + 1] ^= 1;
    } else {
      l = read();
      r = read();
      printf("%lld\n", T.query(1, 1, 1 << n, n, l, r));
    }
  }
  return 0;
}
