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\}. 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ReverseAndSwap solver = new ReverseAndSwap();
        solver.solve(1, in, out);
        out.close();
    }

    static class ReverseAndSwap {
        boolean[] swap = new boolean[19];

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int N = in.nextInt();
            int q = in.nextInt();
            SegmentTree seg = new SegmentTree(N);
            for (int i = 0; i < (1 << N); i++) {
                seg.add(1, 0, (1 << N) - 1, i, in.nextInt(), N - 1);
            }
            while (q-- > 0) {
                int id = in.nextInt();
                if (id == 1) {
                    seg.add(1, 0, (1 << N) - 1, in.nextInt() - 1, in.nextInt(), N - 1);
                } else if (id == 2) {
                    int a = in.nextInt();
                    for (int i = 0; i < a; i++) {
                        swap[i] = !swap[i];
                    }
                } else if (id == 3) {
                    int a = in.nextInt();
                    swap[a] = !swap[a];
                } else {
                    int l = in.nextInt() - 1;
                    int r = in.nextInt() - 1;
                    out.println(seg.sum(1, 0, (1 << N) - 1, l, r, N - 1));
                }
            }
        }

        class SegmentTree {
            long[] sum;

            SegmentTree(int N) {
                sum = new long[4 * (1 << N)];
            }

            void add(int n, int tl, int tr, int x, int k, int l) {
                if (tl == tr) {
                    sum[n] = k;
                } else {
                    int tm = (tl + tr) / 2;
                    if (swap[l]) {
                        if (tm >= x) {
                            add(2 * n + 1, tm + 1, tr, tm + (x - tl) + 1, k, l - 1);
                        } else {
                            add(2 * n, tl, tm, tl + (x - (tm + 1)), k, l - 1);
                        }
                    } else {
                        if (tm >= x) {
                            add(2 * n, tl, tm, x, k, l - 1);
                        } else {
                            add(2 * n + 1, tm + 1, tr, x, k, l - 1);
                        }
                    }
                    sum[n] = sum[2 * n] + sum[2 * n + 1];
                }
            }

            long sum(int n, int tl, int tr, int l, int r, int k) {
                if (l > r) {
                    return 0;
                }
                if (tl == l && tr == r) {
                    return sum[n];
                } else {
                    int tm = (tl + tr) / 2;
                    int leftl = l;
                    int leftr = Math.min(tm, r);
                    int rightl = Math.max(tm + 1, l);
                    int rightr = r;
                    if (swap[k]) {
                        return sum(2 * n + 1, tm + 1, tr, leftl + (tr - tm), leftr + (tr - tm), k - 1) +
                                sum(2 * n, tl, tm, rightl - (tr - tm), rightr - (tr - tm), k - 1);
                    } else {
                        return sum(2 * n, tl, tm, leftl, leftr, k - 1) + sum(2 * n + 1, tm + 1, tr, rightl, rightr, k - 1);
                    }
                }
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

