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.util.*;
import java.io.*;

public class CFA {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    private static final long MOD = 1000L * 1000L * 1000L + 7;
    private static final int[] dx = {0, -1, 0, 1};
    private static final int[] dy = {1, 0, -1, 0};
    private static final String yes = "Yes";
    private static final String no = "No";

    void solve() {
//        int T = nextInt();
        int T = 1;
        for (int i = 0; i < T; i++) {
            helper();
        }
    }


    int[] arr;
    long[] tree;

    void build_tree(int node, int startIndex, int endIndex) {
        if(startIndex > endIndex) return; // Out of range
        if(startIndex == endIndex) { // Leaf node
            tree[node] = arr[startIndex]; // Init value
            return;
        }

        build_tree(node * 2, startIndex, (startIndex + endIndex) / 2); // Init left child
        build_tree(node * 2 + 1, 1 + (startIndex + endIndex) / 2, endIndex); // Init right child
        tree[node] = tree[node * 2] +  tree[node * 2 + 1]; // Init root value
    }

    /**
     * Increment elements at queryIndex with value
     */
    void update_tree(int level, int node, int nodeStartIndex, int nodeEndIndex, int queryIndex, long value) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryIndex || nodeEndIndex < queryIndex) // Current segment is not within range [i, j]
            return;
        if(nodeStartIndex == nodeEndIndex) { // Segment is fully within range
            tree[node] += value;
            return;
        }

        if (!swap[level]) {
            update_tree(level - 1, node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryIndex, value); // Updating left child
            update_tree(level - 1, node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryIndex, value); // Updating right child
        } else {
            update_tree(level - 1, node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryIndex, value); // Updating left child
            update_tree(level - 1, node * 2 + 1, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryIndex, value); // Updating right child
        }

        tree[node] = tree[node * 2] + tree[node * 2 + 1]; // Updating root
    }

    /**
     * Query tree to get max element value within range [queryStartIndex, queryEndIndex]
     */
    long query_tree(int level, int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) {
            return 0; // Out of range!!! change if necessary
        }

        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) {// Current segment is totally within range [i, j]
            return tree[node];
        }

        long q1;
        long q2;
        if (!swap[level]) {
            q1 = query_tree(level - 1, node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
            q2 = query_tree(level - 1, 1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child
        } else {
            q1 = query_tree(level - 1, 1 + node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
            q2 = query_tree(level - 1, node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child
        }
        return q1 + q2;
    }

    boolean[] swap;
    void helper() {
        int n = nextInt();
        int q = nextInt();
        int LIMIT = 20;
        swap = new boolean[LIMIT];
        arr = nextIntArr(1 << n);
        tree = new long[5 * arr.length];

        build_tree(1, 0, arr.length - 1);
        for (int i = 0; i < q; i++) {
            int type = nextInt();
            if (type == 1) {
                int x = nextInt() - 1;
                int k = nextInt();
                long prev = query_tree(n, 1, 0, arr.length - 1, x, x);
                update_tree(n, 1, 0, arr.length - 1, x, k - prev);

            } else if (type == 2) {
                int k = nextInt();
                for (int j = 0; j < k; j++) {
                    swap[j + 1] = !swap[j + 1];
                }
            } else if (type == 3) {
                int k = nextInt();
                swap[k + 1] = !swap[k + 1];
            } else {
                int l = nextInt() - 1;
                int r = nextInt() - 1;

                long res = query_tree(n, 1, 0, arr.length - 1, l, r);
                outln(res);
            }
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }
    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    private void formatPrint(double val) {
        outln(String.format("%.9f%n", val));
    }
    public CFA() {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) {
        new CFA();
    }

    public long[] nextLongArr(int n) {
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() {
        return Double.parseDouble(nextToken());
    }
}