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\}. 
// package com.company;
import java.util.*;
import java.lang.*;
import java.io.*;
//****Use Integer Wrapper Class for Arrays.sort()****
public class EU6 {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] Args)throws Exception{
        FastReader scan=new FastReader(System.in);
        int t=1;
//        t=scan.nextInt();
        while(t-->0){
            int n=scan.nextInt();
            int q=scan.nextInt();
            int[] arr=new int[(int)Math.pow(2,n)];
            for(int i=0;i<arr.length;i++){
                arr[i]=scan.nextInt();
            }
            segTree tree=new segTree(arr);
            for(int i=0;i<q;i++){
                int type=scan.nextInt();
                if(type==1){
                    int x=scan.nextInt();
                    int k=scan.nextInt();
                    tree.update(x-1,k);
                }if(type==2){
                    int k=scan.nextInt();
                    for(int j=k;j>=1;j--){
                        tree.swap[j]^=true;
                    }
                }if(type==3){
                    int k=scan.nextInt();
                    tree.swap[k+1]^=true;
                }if(type==4){
                    int l=scan.nextInt();
                    int r=scan.nextInt();
                    out.println(tree.query(l-1,r-1));
                }
            }
        }
        out.flush();
        out.close();
    }
    static class segTree{
        snode[] arr;
        boolean[] swap;
        int n;
        segTree(int[] ar){
            int x=(int)(Math.ceil(Math.log(ar.length)/Math.log(2)));
            int n=2*(int)Math.pow(2,x)-1;
            this.arr=new snode[n];
            for(int i=0;i<n;i++){
                arr[i]=new snode();
            }
            this.n=ar.length-1;
            construct(0,ar.length-1,ar,0,x);
            swap=new boolean[x+1];
        }
        void construct(int l,int r,int[] ar,int pos,int h){
            if(l==r){
                arr[pos].x=ar[l];
                arr[pos].h=h;
                return;
            }
            int mid=(l+r)/2;
            int li=2*pos+1;
            int ri=2*pos+2;
            construct(l,mid,ar,2*pos+1,h-1);
            construct(mid+1,r,ar,2*pos+2,h-1);
            snode ll=arr[li];
            snode rr=arr[ri];
            arr[pos].x=ll.x+rr.x;
            arr[pos].h=h;
        }
        void update(int i,int nv){
            update(0,n,i,nv,0);
        }
        void update(int l,int r,int i,int nv,int pos){
            if(i==l&&i==r){
                arr[pos].x=nv;
                return;
            }
            if(i<l||i>r){
                return;
            }
            int mid=(l+r)/2;
            int li=2*pos+1;
            int ri=2*pos+2;
            if(swap[arr[pos].h]){
                int temp=li;
                li=ri;
                ri=temp;
            }
            update(l,mid,i,nv,li);
            update(mid+1,r,i,nv,ri);
            snode ll=arr[li];
            snode rr=arr[ri];
            arr[pos].x=ll.x+rr.x;
        }
        long query(int i,int j){
            return query(0,n,i,j,0).x;
        }
        snode query(int l,int r,int i,int j,int pos){
            snode ret=new snode();
            if(i>r||j<l){
                return null;
            }
            if(i<=l&&j>=r){
                ret.x=arr[pos].x;
                return ret;
            }
            int mid=(l+r)/2;
            int li=2*pos+1;
            int ri=2*pos+2;
            if(swap[arr[pos].h]){
                int temp=li;
                li=ri;
                ri=temp;
            }
            snode ll=query(l,mid,i,j,li);
            snode rr=query(mid+1,r,i,j,ri);
            if(ll==null){
                return rr;
            }
            if(rr==null){
                return ll;
            }
            ret.x=ll.x+rr.x;
            return ret;
        }
//        void display(){
//            for(snode i:arr){
//                System.out.println(i.x+" "+i.y);
//            }
//        }
    }
    static class snode{
        long x=0;
        int h=0;
    }
    static class FastReader {

        byte[] buf = new byte[2048];
        int index, total;
        InputStream in;

        FastReader(InputStream is) {
            in = is;
        }

        int scan() throws IOException {
            if (index >= total) {
                index = 0;
                total = in.read(buf);
                if (total <= 0) {
                    return -1;
                }
            }
            return buf[index++];
        }

        String next() throws IOException {
            int c;
            for (c = scan(); c <= 32; c = scan()) ;
            StringBuilder sb = new StringBuilder();
            for (; c > 32; c = scan()) {
                sb.append((char) c);
            }
            return sb.toString();
        }

        int nextInt() throws IOException {
            int c, val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
        long nextLong() throws IOException {
            int c;
            long val = 0;
            for (c = scan(); c <= 32; c = scan()) ;
            boolean neg = c == '-';
            if (c == '-' || c == '+') {
                c = scan();
            }
            for (; c >= '0' && c <= '9'; c = scan()) {
                val = (val << 3) + (val << 1) + (c & 15);
            }
            return neg ? -val : val;
        }
    }
}
