#include <bits/stdc++.h>
using namespace std;
class segtree {
  int n;
  struct node {
    long long val;
    int rev, sw;
    node *left, *right;
    node() : val(0), rev(0), sw(0), left(nullptr), right(nullptr) {}
  } * root;
  void __build(int* x, node*& p, int l, int r) {
    p = new node;
    if (l == r) {
      p->val = x[l - 1];
      return;
    }
    __build(x, p->left, l, ((l + r) >> 1));
    __build(x, p->right, ((l + r) >> 1) + 1, r);
    p->val = p->left->val + p->right->val;
  }
  void push(node* p, const int& l, const int& r) {
    if (l == r) {
      p->rev = 0;
      p->sw = 0;
      return;
    }
    if ((r - l + 1) & p->rev) {
      node* tmp = p->left;
      p->left = p->right;
      p->right = tmp;
      p->rev ^= r - l + 1;
      p->rev ^= (r - l + 1 >> 1);
    }
    p->left->rev ^= p->rev;
    p->right->rev ^= p->rev;
    p->rev = 0;
    if ((r - l + 1) & p->sw) {
      node* tmp = p->left;
      p->left = p->right;
      p->right = tmp;
      p->sw ^= r - l + 1;
    }
    p->left->sw ^= p->sw;
    p->right->sw ^= p->sw;
    p->sw = 0;
  }
  void __replace(const int& idx, const int& k, node* p, int l, int r) {
    push(p, l, r);
    if (l > idx || r < idx) return;
    if (l == r) {
      p->val = k;
      return;
    }
    __replace(idx, k, p->left, l, ((l + r) >> 1));
    __replace(idx, k, p->right, ((l + r) >> 1) + 1, r);
    p->val = p->left->val + p->right->val;
  }
  long long __sum(const int& st, const int& ed, node* p, int l, int r) {
    push(p, l, r);
    if (l > ed || r < st) return 0;
    if (l >= st && r <= ed) return p->val;
    return __sum(st, ed, p->left, l, ((l + r) >> 1)) +
           __sum(st, ed, p->right, ((l + r) >> 1) + 1, r);
  }
  void __print(node* p, int l, int r) {
    push(p, l, r);
    if (l == r) {
      printf("%I64lld ", p->val);
      return;
    }
    __print(p->left, l, ((l + r) >> 1));
    __print(p->right, ((l + r) >> 1) + 1, r);
  }

 public:
  segtree(int m) : n(m), root(nullptr) {}
  void build(int* x) { __build(x, root, 1, 1 << n); }
  void replace(const int& idx, const int& k) {
    __replace(idx, k, root, 1, 1 << n);
  }
  void reverse(const int& k) { root->rev ^= (1 << k); }
  void swap(const int& k) { root->sw ^= (1 << k + 1); }
  long long sum(const int& l, const int& r) {
    return __sum(l, r, root, 1, 1 << n);
  }
  void print() { __print(root, 1, 1 << n); }
};
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  segtree x(n);
  int* y = new int[1 << n];
  for (int i = 0; i < (1 << n); i++) scanf("%d", y + i);
  x.build(y);
  while (q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int idx, k;
      scanf("%d%d", &idx, &k);
      x.replace(idx, k);
    } else if (t == 2) {
      int k;
      scanf("%d", &k);
      x.reverse(k);
    } else if (t == 3) {
      int k;
      scanf("%d", &k);
      x.swap(k);
    } else {
      int l, r;
      scanf("%d%d", &l, &r);
      printf("%I64lld\n", x.sum(l, r));
    }
  }
}
