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>
auto& scan_in = std::cin;
template <typename T>
void MACRO_VAR_Scan(T& t) {
  scan_in >> t;
}
template <typename First, typename... Rest>
void MACRO_VAR_Scan(First& first, Rest&... rest) {
  scan_in >> first;
  MACRO_VAR_Scan(rest...);
}
template <typename T>
void MACRO_VEC_ROW_Init(int n, T& t) {
  t.resize(n);
}
template <typename First, typename... Rest>
void MACRO_VEC_ROW_Init(int n, First& first, Rest&... rest) {
  first.resize(n);
  MACRO_VEC_ROW_Init(n, rest...);
}
template <typename T>
void MACRO_VEC_ROW_Scan(int p, T& t) {
  scan_in >> t[p];
}
template <typename First, typename... Rest>
void MACRO_VEC_ROW_Scan(int p, First& first, Rest&... rest) {
  scan_in >> first[p];
  MACRO_VEC_ROW_Scan(p, rest...);
}
template <typename T>
void MACRO_OUT(const T t) {
  std::cout << t;
}
template <typename First, typename... Rest>
void MACRO_OUT(const First first, const Rest... rest) {
  std::cout << first << " ";
  MACRO_OUT(rest...);
}
template <class S, class T, class U>
bool IN(S a, T x, U b) {
  return a <= x && x < b;
}
template <class T>
inline T CHMAX(T& a, const T b) {
  return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
  return a = (a > b) ? b : a;
}
template <class T>
using V = std::vector<T>;
template <class T>
using VV = V<V<T>>;
template <typename S, typename T>
std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "{";
  for (size_t i = 0; i < v.size(); ++i)
    os << v[i] << ((i + 1 < v.size()) ? ", " : "");
  os << "}";
  return os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& v) {
  os << "{";
  for (auto it = v.cbegin();;) {
    os << *it;
    ++it;
    if (it == v.cend()) {
      os << "}";
      break;
    } else {
      os << ", ";
    }
  }
  return os;
}
template <typename S, typename T>
std::ostream& operator<<(std::ostream& os, const std::map<S, T>& m) {
  os << "{";
  for (auto it = m.cbegin(); it != m.cend();) {
    os << it->first << ":" << it->second;
    ++it;
    os << (it == m.cend() ? "" : ", ");
  }
  os << "}";
  return os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, std::queue<T> q) {
  os << "<";
  while (!q.empty()) {
    os << q.front();
    q.pop();
    os << (q.empty() ? "<" : ", ");
  }
  return os;
}
template <typename T>
std::ostream& operator<<(std::ostream& os, std::stack<T> q) {
  os << ">";
  while (!q.empty()) {
    os << q.top();
    q.pop();
    os << (q.empty() ? "]" : ", ");
  }
  return os;
}
namespace std {
template <typename S, typename T>
class numeric_limits<pair<S, T>> {
 public:
  static constexpr pair<S, T> max() noexcept {
    return {numeric_limits<S>::max(), numeric_limits<T>::max()};
  }
  static constexpr pair<S, T> lowest() noexcept {
    return {numeric_limits<S>::lowest(), numeric_limits<T>::lowest()};
  }
};
}  // namespace std
using i64 = std::int_fast64_t;
using u64 = std::uint_fast64_t;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using PAIR = std::pair<i64, i64>;
using PAIRLL = std::pair<ll, ll>;
constexpr int INFINT = (1 << 30) - 1;
constexpr int INFINT_LIM = (1LL << 31) - 1;
constexpr ll INFLL = 1LL << 60;
constexpr ll INFLL_LIM = (1LL << 62) - 1 + (1LL << 62);
constexpr double EPS = 1e-6;
constexpr i64 MOD = 1000000007;
constexpr double PI = 3.141592653589793238462643383279;
template <class T, size_t N>
void FILL(T (&a)[N], const T& val) {
  for (auto& x : a) x = val;
}
template <class ARY, size_t N, size_t M, class T>
void FILL(ARY (&a)[N][M], const T& val) {
  for (auto& b : a) FILL(b, val);
}
template <class T>
void FILL(std::vector<T>& a, const T& val) {
  for (auto& x : a) x = val;
}
template <class ARY, class T>
void FILL(std::vector<std::vector<ARY>>& a, const T& val) {
  for (auto& b : a) FILL(b, val);
}
struct Node {
  int rev;
  int swp;
  i64 sum;
  Node* ch[2];
};
Node node[600005];
void push(Node* p) {
  if (p->ch == nullptr) return;
  if (p->rev & 1) {
    std::swap(p->ch[0], p->ch[1]);
    p->rev ^= 2;
  }
  for (int k = (0); k < (2); ++k) p->ch[k]->rev ^= p->rev >> 1;
  p->rev = 0;
  if (p->swp & 1) std::swap(p->ch[0], p->ch[1]);
  for (int k = (0); k < (2); ++k) p->ch[k]->swp ^= p->swp >> 1;
  p->swp = 0;
}
void update(Node* p, int x, int k, int l, int r) {
  if (p->ch[0] == nullptr) {
    p->sum = k;
    return;
  }
  push(p);
  if (IN(l, x, (l + r) / 2))
    update(p->ch[0], x, k, l, (l + r) / 2);
  else
    update(p->ch[1], x, k, (l + r) / 2, r);
  p->sum = p->ch[0]->sum + p->ch[1]->sum;
}
i64 query(Node* p, int l, int r, int a, int b) {
  if (l <= a && b <= r) return p->sum;
  if (b <= l || r <= a) return (i64)0;
  push(p);
  return query(p->ch[0], l, r, a, (a + b) / 2) +
         query(p->ch[1], l, r, (a + b) / 2, b);
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  ;
  int L, q;
  MACRO_VAR_Scan(L, q);
  ;
  int n = 1 << L;
  std::vector<int> a(n);
  for (auto& i : a) scan_in >> i;
  ;
  Node* root = &node[0];
  for (int i = (0); i < (n - 1); ++i) {
    node[i].rev = 0;
    node[i].swp = 0;
    node[i].sum = 0;
    node[i].ch[0] = &node[i * 2 + 1];
    node[i].ch[1] = &node[i * 2 + 2];
  }
  for (int i = (0); i < (n); ++i) {
    node[n - 1 + i].rev = 0;
    node[n - 1 + i].swp = 0;
    node[n - 1 + i].sum = a[i];
    node[n - 1 + i].ch[0] = node[n - 1 + i].ch[1] = nullptr;
  }
  for (int i = (n - 1) - 1; i >= (0); --i) {
    node[i].sum = node[i].ch[0]->sum + node[i].ch[1]->sum;
  }
  for (int _ = (0); _ < (q); ++_) {
    int type;
    MACRO_VAR_Scan(type);
    ;
    if (type == 1) {
      int x, k;
      MACRO_VAR_Scan(x, k);
      ;
      --x;
      update(root, x, k, 0, n);
    } else if (type == 2) {
      int k;
      MACRO_VAR_Scan(k);
      ;
      root->rev ^= 1 << (L - k);
    } else if (type == 3) {
      int k;
      MACRO_VAR_Scan(k);
      ;
      root->swp ^= 1 << (L - 1 - k);
    } else {
      int l, r;
      MACRO_VAR_Scan(l, r);
      ;
      --l;
      MACRO_OUT(query(root, l, r, 0, n));
      std::cout << "\n";
      ;
    }
  }
  return 0;
}
