#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1 << 18;
int a[MAXN];
long long s[MAXN << 2];
int h[MAXN << 2];
void build(int id, int l, int r) {
  if (l == r) {
    s[id] = a[l];
    h[id] = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(id << 1, l, mid);
  build(id << 1 | 1, mid + 1, r);
  s[id] = s[id << 1] + s[id << 1 | 1];
  h[id] = h[id << 1] + 1;
}
long long query(int id, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) return s[id];
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (ll <= mid) ret += query(id << 1, l, mid, ll, rr);
  if (rr > mid) ret += query(id << 1 | 1, mid + 1, r, ll, rr);
  return ret;
}
void modify(int id, int l, int r, int pos, int v) {
  if (l == r) {
    s[id] = v;
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid)
    modify(id << 1, l, mid, pos, v);
  else
    modify(id << 1 | 1, mid + 1, r, pos, v);
  s[id] = s[id << 1] + s[id << 1 | 1];
}
int S;
int v = 0;
long long query1(int id, int l, int r, int ll, int rr) {
  if (ll <= l && r <= rr) {
    int LLL = ((v & (S - (1 << h[id]))) ^ l),
        RRR = ((v & (S - (1 << h[id]))) ^ r);
    if (LLL > RRR) swap(LLL, RRR);
    return query(1, 0, S - 1, LLL, RRR);
  }
  int mid = (l + r) >> 1;
  long long ret = 0;
  if (ll <= mid) ret += query1(id << 1, l, mid, ll, rr);
  if (rr > mid) ret += query1(id << 1 | 1, mid + 1, r, ll, rr);
  return ret;
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = 0; i < (1 << n); ++i) scanf("%d", &a[i]);
  build(1, 0, (1 << n) - 1);
  S = (1 << n);
  for (int i = 1; i <= q; ++i) {
    int tp;
    scanf("%d", &tp);
    if (tp == 1) {
      int x, k;
      scanf("%d%d", &x, &k);
      x--;
      x ^= v;
      modify(1, 0, (1 << n) - 1, x, k);
    } else if (tp == 2) {
      int k;
      scanf("%d", &k);
      v ^= (1 << k) - 1;
    } else if (tp == 3) {
      int k;
      scanf("%d", &k);
      v ^= (1 << k);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      l--;
      r--;
      printf("%lld\n", query1(1, 0, (1 << n) - 1, l, r));
    }
  }
  return 0;
}
