#include <bits/stdc++.h>
using namespace std;
int n, q, op, x, y, a[262150], rev[25];
long long sum[1048580];
inline void pushup(int u) { sum[u] = sum[(u << 1)] + sum[(u << 1 | 1)]; }
void build(int u, int l, int r) {
  if (l == r) {
    sum[u] = a[l];
    return;
  }
  int mid = (l + r) >> 1;
  build((u << 1), l, mid);
  build((u << 1 | 1), mid + 1, r);
  pushup(u);
}
void modify(int u, int l, int r, int x, int y, int dep) {
  if (l == r) {
    sum[u] = y;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    modify((u << 1) ^ rev[dep], l, mid, x, y, dep - 1);
  else
    modify((u << 1 | 1) ^ rev[dep], mid + 1, r, x, y, dep - 1);
  pushup(u);
}
long long query(int u, int l, int r, int x, int y, int dep) {
  if (l >= x && r <= y) return sum[u];
  int mid = (l + r) >> 1;
  long long res = 0;
  if (x <= mid) res += query((u << 1) ^ rev[dep], l, mid, x, y, dep - 1);
  if (y > mid) res += query((u << 1 | 1) ^ rev[dep], mid + 1, r, x, y, dep - 1);
  return res;
}
int main() {
  scanf("%d%d", &n, &q);
  for (int i = 1; i <= 1 << n; ++i) scanf("%d", a + i);
  build(1, 1, 1 << n);
  while (q--) {
    scanf("%d%d", &op, &x);
    if (op == 1 || op == 4) scanf("%d", &y);
    if (op == 1) modify(1, 1, 1 << n, x, y, n);
    if (op == 2)
      for (int i = 0; i <= x; ++i) rev[i] ^= 1;
    if (op == 3) rev[x + 1] ^= 1;
    if (op == 4) printf("%lld\n", query(1, 1, 1 << n, x, y, n));
  }
  return 0;
}
