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.*;
import java.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;

public class MainF {

    static int N, Q;
    static int[] A;

    public static void main(String[] args) {
        var sc = new FastScanner(System.in);
        N = sc.nextInt();
        int size = (int)Math.pow(2, N);
        Q = sc.nextInt();
        A = sc.nextIntArray(size);

        RangeSum seg = new RangeSum(N, size);
        for (int i = 0; i < size; i++) {
            seg.set(i, A[i]);
        }

        for (int i = 0; i < Q; i++) {
            int type = sc.nextInt();
            if( type == 1 ) {
                // replace
                int idx = sc.nextInt()-1;
                int v = sc.nextInt();
                seg.set(idx, v);

            } else if( type == 2 ) {
                // reverse
                int k = sc.nextInt();
                seg.reverse[k] = !seg.reverse[k];

            } else if( type == 3 ) {
                // swap
                int k = sc.nextInt();
                seg.swap[k] = !seg.swap[k];

            } else {
                int l = sc.nextInt()-1;
                int r = sc.nextInt()-1;
                long sum = seg.query(l, r);

                System.out.println( sum );
            }
        }
    }

    static class RangeSum {
        int n;
        int size;
        long[] tree;
        boolean[] reverse;
        boolean[] swap;

        public RangeSum(int n, int size) {
            this.n = n;
            this.size = size;
            this.tree = new long[this.size*2];
            reverse = new boolean[n+1];
            swap = new boolean[n+1];
        }

        void set(int idx, int v) {
            _set(idx, v, 0, size-1, n);
        }

        void _set(int idx, int v, int l, int r, int k) {
            if( k == 0 ) {
                idx += size;
                tree[idx] = v;

                while(idx > 1) {
                    idx /= 2;
                    tree[idx] = tree[idx*2] + tree[idx*2+1];
                }
                return;
            }

            int mid = (l+r)/2 + 1;

            if( reverse[k] ) {
                idx = reverseIndex(idx, l, r);
            }

            if( swap[k-1] ) {
                if( idx < mid ) {
                    _set(idx-l+mid, v, mid, r, k-1);

                } else {
                    _set(idx-mid+l, v, l, mid-1, k-1);
                }

            } else {
                if( idx < mid ) {
                    _set(idx, v, l, mid-1, k-1);
                } else {
                    _set(idx, v, mid, r, k-1);
                }
            }
        }

        // [from, to]
        long query(int from, int to) {
            return _query(from, to, 1, 0, size-1, n);
        }

        private long _query(int from, int to, int idx, int l, int r, int k) {
            if (r < from || to < l) return 0;
            if (from == l && r == to) return tree[idx];

            if( reverse[k] ) {
                int revFrom = reverseIndex(from, l, r);
                int revTo = reverseIndex(to, l, r);
                from = revTo;
                to = revFrom;
            }

            int mid = (l+r)/2 + 1;
            if( swap[k-1] ) {
                if( to < mid ) {
                    // [from, to], [x, x] -> [x, x], [from-l+mid, to-l+mid]
                    return _query(from-l+mid, to-l+mid, idx*2+1, mid, r, k-1);

                } else if( mid <= from ) {
                    // [x, x], [from, to] -> [from-mid+l, to-mid+l], [x, x]
                    return _query(from-mid+l, to-mid+l, idx*2, l, mid-1, k-1);

                } else {
                    // [from, to] -> [from, mid-1], [mid, to] -> [l, to-mid+l], [from-l+mid, r]
                    long vl = _query(l, to-mid+l, idx*2, l, mid-1, k-1);
                    long vr = _query(from-l+mid, r, idx*2+1, mid, r, k-1);
                    return vl + vr;
                }

            } else {
                if( to < mid ) {
                    return _query(from, to, idx*2, l, mid-1, k-1);

                } else if( mid <= from ) {
                    return _query(from, to, idx*2+1, mid, r, k-1);

                } else {
                    long vl = _query(from, mid-1, idx*2, l, mid-1, k-1);
                    long vr = _query(mid, to, idx*2+1, mid, r, k-1);
                    return vl + vr;
                }
            }
        }

        int reverseIndex(int idx, int l, int r) {
            return (l+r) - idx;
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private final BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

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

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

        long nextLong() {
            return Long.parseLong(next());
        }

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

        int[] nextIntArray(int n) {
            var a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            var a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            var a = new long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }
    }

    static void writeLines(int[] as) {
        var pw = new PrintWriter(System.out);
        for (var a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        var pw = new PrintWriter(System.out);
        for (var a : as) pw.println(a);
        pw.flush();
    }

    static void writeSingleLine(int[] as) {
        var pw = new PrintWriter(System.out);
        for (var i = 0; i < as.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(as[i]);
        }
        pw.println();
        pw.flush();
    }

    static void debug(Object... args) {
        var j = new StringJoiner(" ");
        for (var arg : args) {
            if (arg == null) j.add("null");
            else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }
}
