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;
class Bin_swaper {
 public:
  vector<long long> d;
  int n;
  int len;
  vector<bool> reversed;
  vector<bool> swaped;
  long long pow(int x, int y) {
    long long res = 1;
    for (int i = 0; i < y; ++i) {
      res *= x;
    }
    return res;
  }
  int log(int x) {
    int res = 0;
    while (x > 1) {
      x = ceil(x / 2.0);
      ++res;
    }
    return res;
  }
  Bin_swaper() {}
  Bin_swaper(int n)
      : len(pow(2, n)),
        d(pow(2, n + 1), 0),
        reversed(n + 1, false),
        swaped(n + 1, false) {
    this->n = n;
  }
  Bin_swaper(const vector<int> &a) {
    n = log(a.size());
    len = pow(2, n);
    d = vector<long long>(pow(2, n + 1), 0);
    reversed = vector<bool>(n + 1, false);
    swaped = vector<bool>(n + 1, false);
    build(a);
  }
  void swap(int k) {
    if (k + 1 <= n) {
      swaped[k + 1] = !swaped[k + 1];
    }
  }
  void reverse(int k) { reversed[k] = !reversed[k]; }
  void build(const vector<int> &a) {
    int i = 0;
    build(1, 0, len - 1, i, a);
  }
  void build(int v, int tl, int tr, int &i, const vector<int> &a) {
    if (tl == tr) {
      d[v] = a[i];
      ++i;
    } else {
      int tm = (tl + tr) / 2;
      build(2 * v, tl, tm, i, a);
      build(2 * v + 1, tm + 1, tr, i, a);
      d[v] = d[2 * v] + d[2 * v + 1];
    }
  }
  void set_item(int v, int tl, int tr, int i, int x, int rev_ind, bool rev) {
    rev = rev ^ reversed[rev_ind];
    if (tl == tr) {
      d[v] = x;
    } else {
      if (!(rev ^ swaped[rev_ind])) {
        int tm = (tl + tr) / 2;
        if (tm >= i) {
          set_item(2 * v, tl, tm, i, x, rev_ind - 1, rev);
        } else {
          set_item(2 * v + 1, tm + 1, tr, i, x, rev_ind - 1, rev);
        }
        d[v] = d[2 * v] + d[2 * v + 1];
      } else {
        int tm = (tl + tr) / 2;
        if (tm >= i) {
          set_item(2 * v + 1, tl, tm, i, x, rev_ind - 1, rev);
        } else {
          set_item(2 * v, tm + 1, tr, i, x, rev_ind - 1, rev);
        }
        d[v] = d[2 * v] + d[2 * v + 1];
      }
    }
  }
  void set_item(int i, int x) { set_item(1, 0, len - 1, i, x, n, 0); }
  long long get_summ(int v, int tl, int tr, int l, int r, int rev_ind,
                     bool rev) {
    rev = rev ^ reversed[rev_ind];
    if (l > r) {
      return 0;
    } else if (tl == l && tr == r) {
      return d[v];
    } else {
      int tm = (tl + tr) / 2;
      if (!(rev ^ swaped[rev_ind])) {
        return get_summ(2 * v, tl, tm, l, min(tm, r), rev_ind - 1, rev) +
               get_summ(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, rev_ind - 1,
                        rev);
      } else {
        return get_summ(2 * v + 1, tl, tm, l, min(tm, r), rev_ind - 1, rev) +
               get_summ(2 * v, tm + 1, tr, max(tm + 1, l), r, rev_ind - 1, rev);
      }
    }
  }
  long long get_summ(int l, int r) {
    return get_summ(1, 0, len - 1, l, r, n, 0);
  }
};
int pow(int x, int y) {
  int res = 1;
  for (int i = 0; i < y; ++i) {
    res *= x;
  }
  return res;
}
int main() {
  int n, q;
  cin >> n >> q;
  int len = pow(2, n);
  vector<int> a(len);
  for (int i = 0; i < len; ++i) {
    cin >> a[i];
  }
  Bin_swaper s(a);
  for (int i = 0; i < q; ++i) {
    int t;
    cin >> t;
    if (t == 1) {
      int x, k;
      cin >> x >> k;
      --x;
      s.set_item(x, k);
    } else if (t == 2) {
      int k;
      cin >> k;
      s.reverse(k);
    } else if (t == 3) {
      int k;
      cin >> k;
      s.swap(k);
    } else if (t == 4) {
      int l, r;
      cin >> l >> r;
      --l;
      --r;
      cout << s.get_summ(l, r) << '\n';
    }
  }
  return 0;
}
