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;
const int maxn = (1 << 18) + 5;
const int maxm = 1000005;
const int inf = 2147483647;
const double eps = 1e-9;
const long long INF = 9223372036854775807ll;
long long qpow(long long a, long long b, long long c) {
  long long ans = 1;
  while (b) {
    if (b & 1) ans = ans * a % c;
    a = a * a % c;
    b >>= 1;
  }
  return ans;
}
inline void rd(int *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(long long *x) {
  int k, m = 0;
  *x = 0;
  for (;;) {
    (k) = getchar();
    if (k == '-') {
      m = 1;
      break;
    }
    if ('0' <= k && k <= '9') {
      *x = k - '0';
      break;
    }
  }
  for (;;) {
    (k) = getchar();
    if (k < '0' || k > '9') break;
    *x = (*x) * 10 + k - '0';
  }
  if (m) (*x) = -(*x);
}
inline void rd(double *x) { scanf("%lf", x); }
inline int rd(char c[]) {
  int i, s = 0;
  for (;;) {
    (i) = getchar();
    if (i != ' ' && i != '\n' && i != '\r' && i != '\t' && i != EOF) break;
  }
  c[s++] = i;
  for (;;) {
    (i) = getchar();
    if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break;
    c[s++] = i;
  }
  c[s] = '\0';
  return s;
}
inline void rd(int a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
inline void rd(long long a[], int n) {
  for (register int i = (0); i < (n); ++i) rd(&a[i]);
}
template <class T, class S>
inline void rd(T *x, S *y) {
  rd(x);
  rd(y);
}
template <class T, class S, class U>
inline void rd(T *x, S *y, U *z) {
  rd(x);
  rd(y);
  rd(z);
}
template <class T, class S, class U, class V>
inline void rd(T *x, S *y, U *z, V *w) {
  rd(x);
  rd(y);
  rd(z);
  rd(w);
}
inline void wr(int x) {
  if (x < 10)
    putchar('0' + x);
  else
    wr(x / 10), wr(x % 10);
}
inline void wr(int x, char c) {
  int s = 0, m = 0;
  char f[10];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(long long x, char c) {
  int s = 0, m = 0;
  char f[20];
  if (x < 0) m = 1, x = -x;
  while (x) f[s++] = x % 10, x /= 10;
  if (!s) f[s++] = 0;
  if (m) putchar('-');
  while (s--) putchar(f[s] + '0');
  putchar(c);
}
inline void wr(double x, char c) {
  printf("%.15f", x);
  putchar(c);
}
inline void wr(const char c[]) {
  int i;
  for (i = 0; c[i] != '\0'; i++) putchar(c[i]);
}
inline void wr(const char x[], char c) {
  int i;
  for (i = 0; x[i] != '\0'; i++) putchar(x[i]);
  putchar(c);
}
template <class T>
inline void wrn(T x) {
  wr(x, '\n');
}
template <class T, class S>
inline void wrn(T x, S y) {
  wr(x, ' ');
  wr(y, '\n');
}
template <class T, class S, class U>
inline void wrn(T x, S y, U z) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, '\n');
}
template <class T, class S, class U, class H>
inline void wrn(T x, S y, U z, H h) {
  wr(x, ' ');
  wr(y, ' ');
  wr(z, ' ');
  wr(h, '\n');
}
template <class T>
inline void wra(T x[], int n) {
  int i;
  if (!n) {
    putchar('\n');
    return;
  }
  for (register int i = (0); i < (n - 1); ++i) wr(x[i], ' ');
  wr(x[n - 1], '\n');
}
int root, n, nn, q, a[maxn], lzsw[maxn * 4], lzre[maxn * 4], tot;
struct Node {
  long long v;
  int lson, rson;
} t[maxn * 4];
int build(int rt, int l, int r) {
  if (l == r) {
    t[rt].v = a[l];
    return rt;
  }
  int mid = l + r >> 1;
  t[rt].lson = build(++tot, l, mid);
  t[rt].rson = build(++tot, mid + 1, r);
  t[rt].v = t[t[rt].lson].v + t[t[rt].rson].v;
  return rt;
}
void pushdown(int rt, int dep) {
  if (lzre[rt] & (1 << dep)) {
    swap(t[rt].lson, t[rt].rson);
    lzre[rt] ^= (1 << (dep + 1));
  }
  lzre[t[rt].lson] ^= lzre[rt];
  lzre[t[rt].rson] ^= lzre[rt];
  lzre[rt] = 0;
  if (lzsw[rt] & (1 << dep)) {
    swap(t[rt].lson, t[rt].rson);
  }
  lzsw[t[rt].lson] ^= lzsw[rt];
  lzsw[t[rt].rson] ^= lzsw[rt];
  lzsw[rt] = 0;
}
void cg(int rt, int l, int r, int x, int k, int dep) {
  if (l == r) {
    t[rt].v = k;
    return;
  }
  int mid = l + r >> 1;
  pushdown(rt, dep);
  if (l <= x && x <= mid)
    cg(t[rt].lson, l, mid, x, k, dep + 1);
  else
    cg(t[rt].rson, mid + 1, r, x, k, dep + 1);
  t[rt].v = t[t[rt].lson].v + t[t[rt].rson].v;
}
void sw(int k) { lzsw[root] ^= (1 << (nn - k - 1)); }
void re(int k) { lzre[root] ^= (1 << (nn - k)); }
long long qry(int rt, int sl, int sr, int l, int r, int dep) {
  if (sl >= l && sr <= r) {
    return t[rt].v;
  }
  pushdown(rt, dep);
  int mid = sl + sr >> 1;
  long long ans = 0;
  if (l <= mid && r >= sl) ans += qry(t[rt].lson, sl, mid, l, r, dep + 1);
  if (l <= sr && r >= mid + 1)
    ans += qry(t[rt].rson, mid + 1, sr, l, r, dep + 1);
  t[rt].v = t[t[rt].lson].v + t[t[rt].rson].v;
  return ans;
}
int main() {
  rd(&n, &q);
  nn = n;
  n = 1 << n;
  rd(a + 1, n);
  root = build(++tot, 1, n);
  while (q--) {
    int op, u, v;
    rd(&op);
    if (op == 1) {
      rd(&u, &v);
      cg(root, 1, n, u, v, 0);
    } else if (op == 2) {
      rd(&u);
      re(u);
    } else if (op == 3) {
      rd(&u);
      sw(u);
    } else if (op == 4) {
      rd(&u, &v);
      wrn(qry(root, 1, n, u, v, 0));
    }
  }
}
