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

public class F {
    static final boolean RUN_TIMING = false;
    static char[] inputBuffer = new char[1 << 20];
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1 << 20);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        int n = 1 << ipar();
        int q = ipar();
        int[] arr = iapar(n);
        SegmentTree tree = new SegmentTree(arr);
        while (q-- > 0) {
            int type = ipar();
            if (type == 1) {
                tree.replace(ipar(), ipar());
            } else if (type == 2) {
                tree.rev(ipar());
            } else if (type == 3) {
                tree.swap(ipar());
            } else {
                out.println(tree.sum(ipar(), ipar()));
            }
            // tree.print();
        }
    }

    private class SegmentTree {
        class Node {
            int k;
            long sum;
            int swap;
            Node left, right;

            public Node() {}

            public Node(long x) {
                sum = x;
                k = 0;
            }
        }

        Node root;
        int n;

        public SegmentTree(int[] arr) {
            n = arr.length;
            root = build(arr, 1, 1, n);
        }

        private Node combine(Node left, Node right) {
            Node node = new Node();
            node.sum = left.sum + right.sum;
            node.k = left.k+1;
            node.left = left;
            node.right = right;
            return node;
        }

        private Node build(int[] arr, int v, int tl, int tr) {
            if (tl == tr) {
                return new Node(arr[tl-1]);
            }
            int tm = (tl+tr)/2;
            Node left = build(arr, v*2, tl, tm);
            Node right = build(arr, v*2+1, tm+1, tr);
            return combine(left, right);
        }

        private void push(Node curr) {
            Node left = curr.left;
            Node right = curr.right;
            if ((curr.swap & (1 << curr.k)) != 0) {
                curr.left = right;
                curr.right = left;
                left = curr.left;
                right = curr.right;
            }
            left.swap ^= curr.swap;
            right.swap ^= curr.swap;
            curr.swap = 0;
        }

        private long sum(Node curr, int tl, int tr, int l, int r) {
            // out.printf("[%d,%d]  [%d,%d]  sum=%d rev=%s k=%d%n", tl, tr, l, r, curr.sum, Integer.toBinaryString(curr.rev), curr.k);
            out.flush();
            if (l > r) {
                return 0;
            }
            if (tl == l && tr == r) {
                return curr.sum;
            }
            push(curr);
            int tm = (tl+tr)/2;
            return sum(curr.left, tl, tm, l, Math.min(tm, r))
                + sum(curr.right, tm+1, tr, Math.max(tm+1, l), r);
        }

        public long sum(int l, int r) {
            return sum(root, 1, n, l, r);
        }

        private Node replace(Node curr, int tl, int tr, int i, int x) {
            // out.printf("[%d,%d]  sum=%d rev=%s k=%d%n", tl, tr, curr.sum, Integer.toBinaryString(curr.rev), curr.k);
            out.flush();
            if (tl == tr) {
                return new Node(x);
            }
            push(curr);
            int tm = (tl+tr)/2;
            if (i <= tm) {
                curr.left = replace(curr.left, tl, tm, i, x);
            } else {
                curr.right = replace(curr.right, tm+1, tr, i, x);
            }
            return combine(curr.left, curr.right);
        }

        public void replace(int i, int x) {
            root = replace(root, 1, n, i, x);
        }

        public void rev(int k) {
            root.swap ^= (1 << (k+1)) - 1;
        }

        public void swap(int k) {
            root.swap ^= 1 << (k+1);
        }

        private void print(Node curr, int tl, int tr) {
            if (tl == tr) {
                out.print(" ");
                out.print(curr.sum);
                return;
            }
            push(curr);
            int tm = (tl+tr)/2;
            print(curr.left, tl, tm);
            print(curr.right, tm+1, tr);
        }

        public void print() {
            print(root, 1, n);
            out.println();
        }
        
        // rev 3 -> swap 2 == rev 2
        // 1 2 3 4 5 6 7 8    1 2 3 4 5 6 7 8
        // 8 7 6 5 4 3 2 1    4 3 2 1 8 7 6 5
        // 4 3 2 1 8 7 6 5
        // swap 2 -> rev 3 == rev 3 -> swap 2
        // 1 2 3 4 5 6 7 8
        // 5 6 7 8 1 2 3 4
        // 4 3 2 1 8 7 6 5
        // swap 1          == rev 2 -> rev 1
        // 1 2 3 4 5 6 7 8    1 2 3 4 5 6 7 8
        // 3 4 1 2 7 8 5 6    4 3 2 1 8 7 6 5
        //                    3 4 1 2 7 8 5 6
        // swap 2          == rev 3 -> rev 2
        // 1 2 3 4 5 6 7 8    1 2 3 4 5 6 7 8
        // 5 6 7 8 1 2 3 4    8 7 6 5 4 3 2 1
        //                    5 6 7 8 1 2 3 4
        // swap 0          == rev 1 -> rev 0
        // 1 2 3 4 5 6 7 8    1 2 3 4 5 6 7 8
        // 2 1 4 3 6 5 8 7    2 1 4 3 6 5 8 7
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        int len = 0;
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            inputBuffer[len] = (char)c;
            len++;
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return new String(inputBuffer, 0, len);
    }

    public String linepar() throws IOException {
        int len = 0;
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            inputBuffer[len] = (char)c;
            len++;
        }
        return new String(inputBuffer, 0, len);
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new F().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time / 1000000.0);
        }
        out.flush();
        in.close();
    }
}
