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 F {
    
    static int mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    static class Node{
    	long val;
    	Node left;
    	Node right;
    	boolean swap;
    	int height;
    	boolean[][] lazy;
    	
    	
    	public Node(int x) {
    		this.val = x;
    		this.left = null;
    		this.right = null;
    		this.height = 0;
    		this.lazy = new boolean[1][2];
		}
    	
    	public Node(Node left, Node right) {
    		this.left = left;
    		this.right = right;
    		this.val = left.val + right.val;
    		this.height = left.height + 1;
    		this.lazy = new boolean[this.height + 1][2];
		}
    	
    	public void updateSwap(){
    		this.swap = !this.swap;
    	}
    	
    	public Node left() {
    		return this.swap ? this.right: this.left;
    	}

    	public Node right() {
    		return this.swap ? this.left: this.right;
    	}
    	
    	
    	public void lazyUpdate(){
    		if(this.left == null) return;
    		
    		for(int i = 1; i <= this.height; i++) {
    			for(int j = 0; j <= 1; j++) {
        			if(lazy[i][j]) {
            			this.left.lazy[i - 1][j] = !this.left.lazy[i - 1][j];
            			this.right.lazy[i - 1][j] = !this.right.lazy[i - 1][j];    				
            			this.lazy[i][j] = false;
        			}    				
    			}
    		}
    		if(this.lazy[0][0]) {
    			updateSwap();
    			this.left.lazy[0][0] = !this.left.lazy[0][0];
    			this.right.lazy[0][0] = !this.right.lazy[0][0];
    			this.lazy[0][0] = false;
    		}
    		
    		if(this.lazy[0][1]) {
    			updateSwap();
    			this.lazy[0][1] = false;
    		}
    	}
    }
    
    static Node build(int[] arr, int l, int r) {
    	if(l == r) {
    		return new Node(arr[l]);
    	}
    	int mid = (r + l) >> 1;
    	return new Node(build(arr, l, mid), build(arr, mid + 1, r));
    }
    
    static Node updateVal(int val, int x, int l, int r, Node root){
    	root.lazyUpdate();
    	if(x == l && x == r) {
    		return new Node(val);
    	}
    	int mid = (r + l) >> 1;
    	if(x <= mid) {
    		return new Node(updateVal(val, x, l, mid, root.left()), root.right());
    	}
    	else {
    		return new Node(root.left(), updateVal(val, x, mid + 1, r, root.right()));
    	}
    }
    
    static long getSum(int x, int y, int l, int r, Node root){
    	root.lazyUpdate();
    	if(x == l && y == r) {
    		return root.val;
    	}
    	int mid = (r + l) >> 1;
    	if(y <= mid) {
    		return getSum(x, y, l, mid, root.left());
    	}
    	else if(x > mid) {
    		return getSum(x, y, mid + 1, r, root.right());    		
    	}
    	else {
    		return getSum(x, mid, l, mid, root.left()) + getSum(mid + 1, y, mid + 1, r, root.right());   		
    	}
    }
    
    static void traverse(Node root, int l, int r) {
    	if(l == r) {
    		debug(l, root.val);
    		return;
    	}
    	int mid = (r + l) >> 1;
    	traverse(root.left(), l, mid);
    	traverse(root.right(), mid + 1, r);
    }
    
    static void solve()
    {
 
        in = new InputReader(System.in);
        out = new PrintWriter(System.out); 
        
        int m = in.nextInt();
        int q = in.nextInt();
        
        int N = 1 << m;
        
        int[] arr = in.nextIntArray(N);
        Node root = build(arr, 0, N - 1);
        
        while(q-- > 0) {
        	int t = in.nextInt();

        	if(t == 1) {
        		int x = in.nextInt() - 1;
        		int k = in.nextInt();
        		root = updateVal(k, x, 0, N - 1, root);
        	}
        	else if(t == 2) {
        		int k = in.nextInt();
        		root.lazy[m - k][0] = !root.lazy[m - k][0];
        	}
        	else if(t == 3) {
        		int k = in.nextInt();
        		if(k == m) continue;
        		root.lazy[m - k - 1][1] = !root.lazy[m - k - 1][1];
        	}
        	else {
        		int x = in.nextInt() - 1;
        		int y = in.nextInt() - 1;
        		out.println(getSum(x, y, 0, N - 1, root));
        	}
        }
        
        out.close();
        
    }
    
    public static void main(String[] args) {
        new Thread(null ,new Runnable(){
            public void run()
            {
                try{
                    solve();
                } catch(Exception e){
                    e.printStackTrace();
                }
            }
        },"1",1<<26).start();
    }
    
    static int[][] graph(int from[], int to[], int n)
    {
        int g[][] = new int[n][];
        int cnt[] = new int[n];
        for (int i = 0; i < from.length; i++) {
            cnt[from[i]]++;
            cnt[to[i]]++;
        }
        for (int i = 0; i < n; i++) {
            g[i] = new int[cnt[i]];
        }
        Arrays.fill(cnt, 0);
        for (int i = 0; i < from.length; i++) {
            g[from[i]][cnt[from[i]]++] = to[i];
            g[to[i]][cnt[to[i]]++] = from[i];
        }
        return g;
    }
    
    static class Pair implements Comparable<Pair>{

        int x,y,i;
        
		Pair (int x,int y,int i){
			this.x=x;
			this.y=y;
			this.i=i;
		}

		Pair (int x,int y){
			this.x=x;
			this.y=y;
		}
	        
		public int compareTo(Pair o) {
			return Integer.compare(this.y,o.y);
			//return 0;
		}

        public boolean equals(Object o) {
            if (o instanceof Pair) {
                Pair p = (Pair)o;
                return p.x == x && p.y == y && p.i==i;
            }
            return false;
        }
        public int hashCode() {
            return new Integer(x).hashCode() * 31 + new Integer(y).hashCode()+new Integer(i).hashCode()*37;
        }
        
        @Override
        public String toString() {
        	return x + " " + y;
        }
    
    } 
    
    static String rev(String s) {
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        return sb.toString();
    }

    static long gcd(long x, long y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }

    static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        } else {
            return gcd(y, x % y);
        }
    }
    
    static int abs(int a, int b) {
        return (int) Math.abs(a - b);
    }

    static long abs(long a, long b) {
        return (long) Math.abs(a - b);
    }

    static int max(int a, int b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }

    static int min(int a, int b) {
        if (a > b) {
            return b;
        } else {
            return a;
        }
    }

    static long max(long a, long b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }

    static long min(long a, long b) {
        if (a > b) {
            return b;
        } else {
            return a;
        }
    }

    static long pow(long n, long p, long m) {
        long result = 1;
        if (p == 0) {
            return 1;
        }
        while (p != 0) {
            if (p % 2 == 1) {
                result *= n;
            }
            if (result >= m) {
                result %= m;
            }
            p >>= 1;
            n *= n;
            if (n >= m) {
                n %= m;
            }
        }
        return result;
    }

    static long pow(long n, long p) {
        long result = 1;
        if (p == 0) {
            return 1;
        }
        if (p == 1) {
            return n;
        }
        while (p != 0) {
            if (p % 2 == 1) {
                result *= n;
            }
            p >>= 1;
            n *= n;
        }
        return result;
    }
   
    static void debug(Object... o) {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }

        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

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

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

        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }

    }
}    

