You are given an array a of length 2^n. You should process q queries on it. Each query has one of the following 4 types: 

  1. Replace(x, k) — change a_x to k; 
  2. Reverse(k) — reverse each subarray [(i-1) ⋅ 2^k+1, i ⋅ 2^k] for all i (i ≥ 1); 
  3. Swap(k) — swap subarrays [(2i-2) ⋅ 2^k+1, (2i-1) ⋅ 2^k] and [(2i-1) ⋅ 2^k+1, 2i ⋅ 2^k] for all i (i ≥ 1); 
  4. Sum(l, r) — print the sum of the elements of subarray [l, r]. 



Write a program that can quickly process given queries.

Input

The first line contains two integers n, q (0 ≤ n ≤ 18; 1 ≤ q ≤ 10^5) — the length of array a and the number of queries.

The second line contains 2^n integers a_1, a_2, …, a_{2^n} (0 ≤ a_i ≤ 10^9).

Next q lines contains queries — one per line. Each query has one of 4 types: 

  * "1 x k" (1 ≤ x ≤ 2^n; 0 ≤ k ≤ 10^9) — Replace(x, k); 
  * "2 k" (0 ≤ k ≤ n) — Reverse(k); 
  * "3 k" (0 ≤ k < n) — Swap(k); 
  * "4 l r" (1 ≤ l ≤ r ≤ 2^n) — Sum(l, r). 



It is guaranteed that there is at least one Sum query.

Output

Print the answer for each Sum query.

Examples

Input


2 3
7 4 9 9
1 2 8
3 1
4 2 4


Output


24


Input


3 8
7 0 8 8 7 1 5 2
4 3 7
2 1
3 2
4 1 6
2 3
1 5 16
4 8 8
3 0


Output


29
22
1

Note

In the first sample, initially, the array a is equal to \{7,4,9,9\}.

After processing the first query. the array a becomes \{7,8,9,9\}.

After processing the second query, the array a_i becomes \{9,9,7,8\}

Therefore, the answer to the third query is 9+7+8=24.

In the second sample, initially, the array a is equal to \{7,0,8,8,7,1,5,2\}. What happens next is: 

  1. Sum(3, 7) → 8 + 8 + 7 + 1 + 5 = 29; 
  2. Reverse(1) → \{0,7,8,8,1,7,2,5\}; 
  3. Swap(2) → \{1,7,2,5,0,7,8,8\}; 
  4. Sum(1, 6) → 1 + 7 + 2 + 5 + 0 + 7 = 22; 
  5. Reverse(3) → \{8,8,7,0,5,2,7,1\}; 
  6. Replace(5, 16) → \{8,8,7,0,16,2,7,1\}; 
  7. Sum(8, 8) → 1; 
  8. Swap(0) → \{8,8,0,7,2,16,1,7\}. 
#include <bits/stdc++.h>
using namespace std;
void init();
void solve();
int main() {
  try {
    init();
    solve();
  } catch (...) {
    return 0;
  }
  return 0;
}
template <class T>
inline bool checkMin(T& a, T b) {
  return (a > b ? a = b, 1 : 0);
}
template <class T>
inline bool checkMax(T& a, T b) {
  return (a < b ? a = b, 1 : 0);
}
class Scanner {
 private:
  istream& ist;

 public:
  Scanner(istream& in) : ist(in) {}
  string next() {
    string r;
    ist >> r;
    return r;
  }
  string nextLine() {
    string r;
    getline(ist, r);
    return r;
  }
  long long nextInt() {
    long long r;
    ist >> r;
    return r;
  }
  double nextDouble() {
    double r;
    ist >> r;
    return r;
  }
  char nextChar() {
    char r;
    ist >> r;
    return r;
  }
};
Scanner sc(cin);
void ALERT(bool judgememt, const char* phrase) {
  if (judgememt) {
    puts(phrase);
    throw "ALERT";
  }
}
bool alert(bool judgememt, const char* phrase) {
  if (judgememt) puts(phrase);
  return judgememt;
}
const long long N = 1200005;
namespace STree {
long long rev[N], swp[N];
struct Node {
  long long val, dep;
  Node *l, *r;
  long long lo_rev, go_rev, go_swap;
  Node() {
    val = dep = lo_rev = go_rev = go_swap = 0;
    l = r = NULL;
  }
  void pushRev() {
    swap(l, r);
    lo_rev ^= 1;
  }
  void pushSwap() { swap(l, r); }
  void pushUp() {
    if (rev[dep] > go_rev) {
      if ((rev[dep] - go_rev) % 2 == 1) pushRev();
      go_rev = rev[dep];
    }
    if (swp[dep] > go_swap) {
      if ((swp[dep] - go_swap) % 2 == 1) pushSwap();
      go_swap = swp[dep];
    }
    val = 0;
    if (l) val += l->val;
    if (r) val += r->val;
  }
  void pushDown() {
    if (rev[dep] > go_rev) {
      if ((rev[dep] - go_rev) % 2 == 1) pushRev();
      go_rev = rev[dep];
    }
    if (swp[dep] > go_swap) {
      if ((swp[dep] - go_swap) % 2 == 1) pushSwap();
      go_swap = swp[dep];
    }
    if (lo_rev == 1) {
      if (l) l->pushRev();
      if (r) r->pushRev();
    }
    lo_rev = 0;
  }
};
Node p[N], *second;
long long cnt;
void init() {
  memset(rev, 0, sizeof(rev));
  memset(swp, 0, sizeof(swp));
  second = &p[0];
  cnt = 1;
}
Node* newNode() { return &p[cnt++]; }
void build(long long l, long long r, long long a[], Node* u,
           long long deep = 0) {
  u->dep = deep;
  if (l == r) {
    u->val = a[l];
    return;
  }
  long long mid = (l + r) / 2;
  build(l, mid, a, u->l = newNode(), deep + 1);
  build(mid + 1, r, a, u->r = newNode(), deep + 1);
  u->pushUp();
}
void modify(long long w, long long _val, long long l, long long r, Node* u) {
  u->pushDown();
  if (l == r) {
    u->val = _val;
    return;
  }
  long long mid = (l + r) / 2;
  if (w <= mid)
    modify(w, _val, l, mid, u->l);
  else
    modify(w, _val, mid + 1, r, u->r);
  u->pushUp();
}
long long query(long long l, long long r, long long sl, long long sr, Node* u) {
  u->pushDown();
  if (sl <= l && sr >= r) {
    return u->val;
  }
  long long mid = (l + r) / 2, ans = 0;
  if (sl <= mid) ans += query(l, mid, sl, sr, u->l);
  if (sr > mid) ans += query(mid + 1, r, sl, sr, u->r);
  ;
  ;
  ;
  return ans;
}
void pushSwap(long long dep) { swp[dep]++; }
void pushRev(long long dep) { rev[dep]++; }
}  // namespace STree
long long a[N];
long long t, n, q;
void init() {
  STree::init();
  scanf("%lld%lld", &t, &q);
  n = (1 << t);
  for (long long i = 0; i < n; i++) scanf("%lld", &a[i]);
  STree::build(0, n - 1, a, STree::second);
}
void solve() {
  while (q--) {
    long long o;
    scanf("%lld", &o);
    if (o == 1) {
      long long x, k;
      scanf("%lld%lld", &x, &k);
      x--;
      STree::modify(x, k, 0, n - 1, STree::second);
    } else if (o == 2) {
      long long k;
      scanf("%lld", &k);
      STree::pushRev(t - k);
    } else if (o == 3) {
      long long k;
      scanf("%lld", &k);
      STree::pushSwap(t - k - 1);
    } else {
      long long l, r;
      scanf("%lld%lld", &l, &r);
      l--;
      r--;
      printf("%lld\n", STree::query(0, n - 1, l, r, STree::second));
    }
  }
}
