#include <bits/stdc++.h>
using namespace std;
struct node {
  node(long long vl, int sz) {
    val = vl;
    size = sz;
    left = NULL;
    right = NULL;
  }
  unordered_map<int, int> upd1;
  unordered_map<int, int> upd2;
  long long val;
  int size;
  node *left, *right;
};
struct str {
  node *root = NULL;
  void init(int sz) { root = new node(0ll, sz); }
  void push(node *v) {
    if (v->size == 0) {
      return;
    }
    short cnt = 0;
    for (auto to : v->upd1) {
      if (to.first >= v->size) {
        cnt += to.second;
      }
      if (v->size > 1) {
        v->left->upd1[to.first] += to.second;
        v->right->upd1[to.first] += to.second;
      }
    }
    for (auto to : v->upd2) {
      if (to.first == v->size - 1) {
        cnt += to.second;
      } else if (to.first < v->size - 1) {
        if (v->size > 1) {
          v->left->upd2[to.first] += to.second;
          v->right->upd2[to.first] += to.second;
        }
      }
    }
    if (cnt % 2) swap(v->left, v->right);
    for (auto to : v->upd1) v->upd1[to.first] = 0;
    for (auto to : v->upd2) v->upd2[to.first] = 0;
  }
  void upd(int pos, long long val, node *v) {
    push(v);
    if (v->size != 0) {
      if (v->left == NULL) {
        v->left = new node(0, v->size - 1);
      }
      if (v->right == NULL) {
        v->right = new node(0, v->size - 1);
      }
    }
    if (v->size == 0) {
      v->val = val;
      return;
    }
    int tm = 1 << (v->size - 1);
    if (pos <= tm) {
      upd(pos, val, v->left);
    } else {
      upd(pos - tm, val, v->right);
    }
    v->val = v->left->val + v->right->val;
  }
  long long get(int l, int r, node *v) {
    push(v);
    if (r - l + 1 <= 0) return 0;
    if ((1 << v->size) == r - l + 1) return v->val;
    int tm = 1 << (v->size - 1);
    return get(l, min(r, tm), v->left) + get(max(l - tm, 1), r - tm, v->right);
  }
} T;
void solve() {
  int n, q;
  cin >> n >> q;
  T.init(n);
  for (int i = 1; i <= (1 << n); i++) {
    int x;
    cin >> x;
    T.upd(i, x, T.root);
  }
  for (int i = 1; i <= q; i++) {
    int type;
    cin >> type;
    if (type == 1) {
      int pos, val;
      cin >> pos >> val;
      T.upd(pos, val, T.root);
    } else if (type == 2) {
      int k;
      cin >> k;
      T.root->upd1[k]++;
    } else if (type == 3) {
      int k;
      cin >> k;
      T.root->upd2[k]++;
    } else {
      int l, r;
      cin >> l >> r;
      cout << T.get(l, r, T.root) << endl;
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  ;
  int t;
  for (int i = 1; i <= 1; i++) {
    solve();
  }
}
