#include <bits/stdc++.h>
using namespace std;
struct segment_tree {
  struct st_node {
    long long val;
    int r, l;
    int inv;
  };
  int n, bits;
  vector<int> data, lvl;
  int identifier = 0;
  vector<st_node> container;
  segment_tree(int n, int bits)
      : n(n), bits(bits), container(4 * n + 1), data(n), lvl(bits + 2) {}
  void build() { build(0, 1, n + 1); }
  void build(int node, int l, int r) {
    auto &x = container[node];
    if (l + 1 == r) {
      x.val = data[l - 1];
      return;
    }
    x.l = ++identifier;
    x.r = ++identifier;
    int mid = (l + r) / 2;
    build(x.l, l, mid);
    build(x.r, mid, r);
    x.val = container[x.l].val + container[x.r].val;
  }
  void update(int v, int val) { update(0, 1, n + 1, v, val, bits); }
  void update(int node, int l, int r, int v, int val, int curlvl) {
    auto x = container[node];
    if (l + 1 == r) {
      container[node].val = val;
      return;
    }
    push_lazy(node);
    if (lvl[curlvl]) swap(x.r, x.l);
    int mid = (l + r) / 2;
    if (v < mid)
      update(x.l, l, mid, v, val, curlvl - 1);
    else
      update(x.r, mid, r, v, val, curlvl - 1);
    container[node].val = container[x.l].val + container[x.r].val;
  }
  long long query(int x, int y) { return query(0, 1, n + 1, x, y + 1, bits); }
  long long query(int node, int a, int b, int x, int y, int curlvl) {
    auto cur = container[node];
    if (x <= a && b <= y) {
      return cur.val;
    }
    push_lazy(node);
    int mid = (a + b) / 2;
    if (lvl[curlvl]) swap(cur.r, cur.l);
    if (y <= mid)
      return query(cur.l, a, mid, x, y, curlvl - 1);
    else if (x >= mid)
      return query(cur.r, mid, b, x, y, curlvl - 1);
    else
      return query(cur.l, a, mid, x, y, curlvl - 1) +
             query(cur.r, mid, b, x, y, curlvl - 1);
  }
  void push_lazy(int node) {
    auto cur = container[node];
    if (cur.inv) {
      swap(container[cur.r], container[cur.l]);
      container[cur.l].inv ^= 1;
      container[cur.r].inv ^= 1;
      container[node].inv = 0;
    }
  };
  void q1(int x, int k) { update(x, k); }
  void q2(int k) {
    for (int i = 0; i <= k; ++i) lvl[i] ^= 1;
  }
  void q3(int k) { lvl[k + 1] ^= 1; }
  long long q4(int l, int r) { return query(l, r); }
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  long long t, n, q;
  cin >> n >> q;
  long long cant = (1 << n);
  segment_tree st(cant, n);
  for (auto &x : st.data) cin >> x;
  st.build();
  long long x, k, l, r;
  while (q--) {
    cin >> t;
    if (t == 1) {
      cin >> x >> k;
      st.q1(x, k);
    } else if (t == 2) {
      cin >> k;
      st.q2(k);
    } else if (t == 3) {
      cin >> k;
      st.q3(k);
    } else {
      cin >> l >> r;
      cout << st.q4(l, r) << "\n";
    }
  }
  return 0;
}
