#include <bits/stdc++.h>
using namespace std;
vector<int> lg((1 << 18) + 1);
struct SeT {
  vector<int64_t> dat;
  vector<int> rev;
  SeT() {}
  void build(int p, int L, int R, vector<int> &a) {
    if (R - L == 1) return dat[p] = a[L], void();
    build((rev[lg[R - L]] == 0 ? p * 2 + 1 : p * 2 + 2), L, (L + R) / 2, a);
    build((rev[lg[R - L]] == 0 ? p * 2 + 2 : p * 2 + 1), (L + R) / 2, R, a);
    dat[p] = dat[(rev[lg[R - L]] == 0 ? p * 2 + 2 : p * 2 + 1)] +
             dat[(rev[lg[R - L]] == 0 ? p * 2 + 1 : p * 2 + 2)];
  }
  void init(int n, vector<int> &a) {
    dat.resize(4 * (1 << n));
    rev.resize(n + 2);
    build(0, 0, 1 << n, a);
  }
  void Swap(int k) { rev[k + 1] ^= 1; }
  void Reverse(int k) {
    for (int i = 1; i <= k; ++i) rev[i] ^= 1;
  }
  void Replace(int p, int L, int R, int x, int k) {
    if (R - L == 1) {
      dat[p] = k;
      return;
    }
    if (x < (L + R) / 2)
      Replace((rev[lg[R - L]] == 0 ? p * 2 + 1 : p * 2 + 2), L, (L + R) / 2, x,
              k);
    if (x >= (L + R) / 2)
      Replace((rev[lg[R - L]] == 0 ? p * 2 + 2 : p * 2 + 1), (L + R) / 2, R, x,
              k);
    dat[p] = dat[(rev[lg[R - L]] == 0 ? p * 2 + 1 : p * 2 + 2)] +
             dat[(rev[lg[R - L]] == 0 ? p * 2 + 2 : p * 2 + 1)];
  }
  int64_t Sum(int p, int L, int R, int l, int r) {
    if (l <= L && R <= r) return dat[p];
    int64_t res = 0;
    if (l < (L + R) / 2)
      res += Sum((rev[lg[R - L]] == 0 ? p * 2 + 1 : p * 2 + 2), L, (L + R) / 2,
                 l, r);
    if (r > (L + R) / 2)
      res += Sum((rev[lg[R - L]] == 0 ? p * 2 + 2 : p * 2 + 1), (L + R) / 2, R,
                 l, r);
    return res;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  for (int i = 0; i <= 1 << 18; ++i) lg[i] = log2(i);
  int n, q;
  cin >> n >> q;
  vector<int> a(1 << n);
  for (int i = 0; i < 1 << n; ++i) cin >> a[i];
  SeT tree;
  tree.init(n, a);
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x, v;
      cin >> x >> v;
      x--;
      tree.Replace(0, 0, 1 << n, x, v);
    } else if (op == 2) {
      int k;
      cin >> k;
      tree.Reverse(k);
    } else if (op == 3) {
      int k;
      cin >> k;
      tree.Swap(k);
    } else if (op == 4) {
      int l, r;
      cin >> l >> r;
      l--, r--;
      cout << tree.Sum(0, 0, 1 << n, l, r + 1) << endl;
    }
  }
  return 0;
}
