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

public class Main  {

    public BufferedReader in;
    public PrintStream out;

    public boolean log_enabled = false;
    
    public boolean multiply_tests = false;

    private class TestCase {

        int n;
        long[] a;

        int[] r_count;
        
        private class Tree
        {
            int d, l, r;
            long s, ss;

            Tree L = null, R = null;

            public Tree(int _d, int _l, int _r)
            {
                d = _d;
                l = 0;
                r = _r - _l;
                
                if (d>0)
                {
                    int c = (_l+_r) / 2;
                    L = new Tree(d-1, _l, c);
                    R = new Tree(d-1, c+1, _r);

                    s = L.s + R.s;
                }
                else
                {
                    s = a[_l];
                }
            }

            public void replace(int x, int k)
            {
                if (d==0)
                {
                    s = k;
                }
                else
                {
                    int c = (l+r) / 2;

                    if (x <= c)
                    {
                        if (r_count[d] % 2 == 0)
                        {
                            L.replace(x, k);
                        }
                        else
                        {
                            R.replace(x, k);
                        }
                    }
                    else
                    {
                        x = x- c -1;
                        
                        if (r_count[d] % 2 == 0)
                        {
                            R.replace(x, k);
                        }
                        else
                        {
                            L.replace(x, k);
                        }
                    }
                    
                    s = L.s + R.s;
                }
            }

            public long sum(int _l, int _r)
            {
                if (d == 0)
                {
                    return s;
                }
                
                if ((_l==l)&&(_r==r))
                {
                    return s;
                }
                
                int c = (l+r) / 2;

                Tree _L, _R;

                if (r_count[d] % 2 == 0)
                {
                    _L = L;
                    _R = R;
                }
                else{
                    _L = R;
                    _R = L;
                }
                
                if (_r <= c)
                {
                    return _L.sum(_l, _r);
                }

                if (_l>c)
                {
                    return _R.sum(_l-c-1, _r-c-1);
                }

                ss = 0;
                if (_l <= c)
                {
                    ss += _L.sum(_l, c);
                }

                if (_r > c)
                {
                    ss += _R.sum(0, _r - c - 1);
                }

                return ss;
            }

            public void output()
            {
                if (d == 0)
                {
                    out.printf(" %d", s);
                    return;
                }
                
                if (r_count[d] % 2 == 0)
                {
                    L.output();
                    R.output();
                }
                else
                {
                    R.output();
                    L.output();
                }
            }
        }
        
        public void output_test()
        {
            int i,n = 4*4*4*4*4*4*4*4*4;
            
            out.println("18 100000");
            for (i=0; i<n; i++)
            {
                out.print(" 1");
            }
            out.println();
            
            for (i=0; i<100000; i++)
            {
                out.printf("4 2 %d\n", n-1);
            }
            
        }

        public Object solve() {
            
            n = readInt();
            
//            if (n==0)
//            {
//                output_test();
//                return null;
//            }
            
            int q = readInt();
            
            int z = 1;
            int i;

            for (i=0; i<n; i++)
            {
                z *= 2;
            }

            a = new long[z];
            readLongArray(a, z);

            Tree root = new Tree(n, 0, z-1);

            
            r_count = new int[n+1];
            

            Arrays.fill(r_count, 0);
            
long[] results = new long[q];
int sc = 0;

            int x, k, l, r, j;
            for (i=0; i<q; i++)
            {
                int t = readInt();
                if (t==1)
                {
                    x = readInt(); k = readInt();
                    root.replace(x-1, k);
                }

                if (t==2)
                {
                    k = readInt();
                    for (j=1; j<=k; j++)
                    {
                        r_count[j] ++;
                    }
                }

                if (t==3)
                {
                    k = readInt();
                    r_count[k+1] ++;
                }

                if (t==4)
                {
                    l = readInt()-1;
                    r = readInt()-1;
                    

                    results[sc++] =  root.sum(l,r);
                }
                else
                {
                  /*  root.output();
                    out.println(); */
                }
            }

            printArray(results, sc);

                          
            
            return null;
            
            //return strf("%f", 0);
            
            //out.printf("Case #%d: \n", caseNumber);
            //return null;
        }
        
        public int caseNumber;
        
        TestCase(int number) {
            caseNumber = number;
        }
        
        public void run(){
            Object r = this.solve();
            
            if ((r != null))
            {
                //outputCaseNumber(r);
                out.println(r);
            }
        }
        
        public String impossible(){
            return "IMPOSSIBLE";
        }
        
        public String strf(String format, Object... args)
        {
            return String.format(format, args);
        }
        
//        public void outputCaseNumber(Object r){
//            //out.printf("Case #%d:", caseNumber);
//            if (r != null)
//            {
//              //  out.print(" ");
//                out.print(r);
//            }
//            out.print("\n");
//        }
    }

    public void run() {
        //while (true)
        {
            int t = multiply_tests ?  readInt() : 1;
            for (int i = 0; i < t; i++) {
                TestCase T = new TestCase(i + 1);
                T.run();
            }
        }
    }
    

    
    public Main(BufferedReader _in, PrintStream _out){
        in = _in;
        out = _out;
    }
    

    public static void main(String args[]) {
        Locale.setDefault(Locale.US);
        Main S;
        try {
            S = new Main(
                        new BufferedReader(new InputStreamReader(System.in)),
                        System.out
                );
        } catch (Exception e) {
            return;
        }
        
        S.run();
        
    }

    private StringTokenizer tokenizer = null;

    public int readInt() {
        return Integer.parseInt(readToken());
    }

    public long readLong() {
        return Long.parseLong(readToken());
    }

    public double readDouble() {
        return Double.parseDouble(readToken());
    }

    public String readLn() {
        try {
            String s;
            while ((s = in.readLine()).length() == 0);
            return s;
        } catch (Exception e) {
            return "";
        }
    }

    public String readToken() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        } catch (Exception e) {
            return "";
        }
    }

    public int[] readIntArray(int n) {
        int[] x = new int[n];
        readIntArray(x, n);
        return x;
    }

    public void readIntArray(int[] x, int n) {
        for (int i = 0; i < n; i++) {
            x[i] = readInt();
        }
    }
    
    public long[] readLongArray(int n) {
        long[] x = new long[n];
        readLongArray(x, n);
        return x;
    }

    public void readLongArray(long[] x, int n) {
        for (int i = 0; i < n; i++) {
            x[i] = readLong();
        }
    }

    public void logWrite(String format, Object... args) {
        if (!log_enabled) {
            return;
        }

        out.printf(format, args);
    }

    public void printArray(long[] a, int n)
    {
    long x;
        int  i, l = 0;
        for (i=0; i<n; i++)
        {
            x = a[i];
            
            if (x<0)
            {
                x = -x;
                l++;
            }
            
            if (x==0)
            {
                l++;
            }
            else
            {
                while (x>0)
                {
                    x /= 10;
                    l++;
                }
            }
        }
        
        l += n-1;
        
        char[] s = new char[l];
        
        l--;
        boolean z;
        for (i=n-1; i>=0;  i--)
        {
            x = a[i];
            z = false;            
            if (x<0)
            {
                x = -x;
                z = true;
            }
            
            do{
                s[l--] = (char)('0' + (x % 10));
                x /= 10;
            } while (x>0);
            
            if (z)
            {
                s[l--] = '-';
            }
            
            if (i>0)
            {
                s[l--] = '\n';
            }
        }
        
        out.println(new String(s));
    }

    public void readLongArrayBuf(long[] x, int n) {
        
        char[]buf = new char[1000000];
        long r = -1;
        int k= 0, l = 0;
        long d;
        
        while (true)
        {
            try{
                l = in.read(buf, 0, 1000000);
            }
            catch(Exception E){};
            
            for (int i=0; i<l; i++)
            {
                if (('0'<=buf[i])&&(buf[i]<='9'))
                {
                    if (r == -1)
                    {
                        r = 0;
                    }
                    d = buf[i] - '0';
                    r = 10 * r + d;
                }
                else
                {
                    if (r != -1)
                    {
                        x[k++] = r;
                    }
                    
                    r = -1;
                }
            }
            
            if (l<1000000)
                return;
        }
    }
}
