#include <bits/stdc++.h>
using namespace std;
int read() {
  char ch = getchar();
  int x = 0, pd = 0;
  while (ch < '0' || ch > '9') pd ^= ch == '-', ch = getchar();
  while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
  return pd ? -x : x;
}
const int maxn = 300005;
int n, m, N;
bool cg[22];
long long sum[maxn << 2];
void pushup(int rt) { rt[sum] = (rt << 1)[sum] + (rt << 1 | 1)[sum]; }
void build(int rt, int l, int r) {
  if (l == r) {
    rt[sum] = read();
    return;
  }
  int mid = (l + r) >> 1;
  build((rt << 1), l, mid), build((rt << 1 | 1), mid + 1, r);
  pushup(rt);
}
void update(int rt, int l, int r, int x, int y, int dep) {
  if (l == r) {
    rt[sum] = y;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update((rt << 1) ^ cg[dep], l, mid, x, y, dep - 1);
  else
    update((rt << 1 | 1) ^ cg[dep], mid + 1, r, x, y, dep - 1);
  pushup(rt);
}
long long query(int rt, int l, int r, int L, int R, int dep) {
  if (L <= l && r <= R) return rt[sum];
  int mid = (l + r) >> 1;
  if (R <= mid) return query((rt << 1) ^ cg[dep], l, mid, L, R, dep - 1);
  if (L > mid) return query((rt << 1 | 1) ^ cg[dep], mid + 1, r, L, R, dep - 1);
  return query((rt << 1) ^ cg[dep], l, mid, L, R, dep - 1) +
         query((rt << 1 | 1) ^ cg[dep], mid + 1, r, L, R, dep - 1);
}
int main() {
  n = read(), m = read();
  N = 1 << n;
  build(1, 1, N);
  while (m--) {
    int opt = read(), x = read(), y;
    if (opt == 2) {
      for (int i = x; i >= 0; i--) cg[i] ^= 1;
    } else if (opt == 3)
      cg[x + 1] ^= 1;
    else {
      y = read();
      if (opt == 1)
        update(1, 1, N, x, y, n);
      else
        printf("%lld\n", query(1, 1, N, x, y, n));
    }
  }
  return 0;
}
