#include <bits/stdc++.h>
using namespace std;
int n, q;
long long tree[(1 << 20) + 5];
bool rev[20];
void update(int pos, int k, int kir, int kan, int x, int val) {
  if (x == kir && kan == x) {
    tree[pos] = val;
    return;
  }
  if (x < kir || kan < x) return;
  int mid = (kir + kan) / 2;
  if (!rev[k]) {
    update(pos * 2, k - 1, kir, mid, x, val);
    update(pos * 2 + 1, k - 1, mid + 1, kan, x, val);
  } else {
    update(pos * 2 + 1, k - 1, kir, mid, x, val);
    update(pos * 2, k - 1, mid + 1, kan, x, val);
  }
  tree[pos] = tree[pos * 2] + tree[pos * 2 + 1];
}
long long query(int pos, int k, int kir, int kan, int qkir, int qkan) {
  if (qkir <= kir && kan <= qkan) return tree[pos];
  if (kan < qkir || qkan < kir) return 0;
  int mid = (kir + kan) / 2;
  if (!rev[k]) {
    long long a = query(pos * 2, k - 1, kir, mid, qkir, qkan);
    long long b = query(pos * 2 + 1, k - 1, mid + 1, kan, qkir, qkan);
    return a + b;
  } else {
    long long a = query(pos * 2, k - 1, mid + 1, kan, qkir, qkan);
    long long b = query(pos * 2 + 1, k - 1, kir, mid, qkir, qkan);
    return a + b;
  }
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= (1 << n); i++) {
    int x;
    scanf("%d", &x);
    update(1, n, 1, (1 << n), i, x);
  }
  while (q--) {
    int t;
    scanf("%d", &t);
    int x, k;
    if (t == 1) {
      scanf("%d %d", &x, &k);
      update(1, n, 1, (1 << n), x, k);
    }
    if (t == 2) {
      scanf("%d", &k);
      for (int i = 1; i <= k; i++) rev[i] ^= 1;
    }
    if (t == 3) {
      scanf("%d", &k);
      rev[k + 1] ^= 1;
    }
    if (t == 4) {
      int l, r;
      scanf("%d %d", &l, &r);
      printf("%lld\n", query(1, n, 1, (1 << n), l, r));
    }
  }
}
