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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public class F {

	public static void main(String[] args) {
		FastScanner fs=new FastScanner();
		int logn=fs.nextInt();
		int nQ=fs.nextInt();
		flipped=new boolean[logn+1];
		int[] a=fs.readArray(1<<logn);
		SegTree st=new SegTree(0, (1<<logn)-1, logn, a);
		PrintWriter out=new PrintWriter(System.out);
		
		for (int qq=0; qq<nQ; qq++) {
			int type=fs.nextInt();
			if (type==1) {
				int index=fs.nextInt()-1, value=fs.nextInt();
				st.pointUpdate(index, value);
			}
			else if (type==2) {
				//reverse
				int k=fs.nextInt();
				for (int i=0; i<=k; i++) flipped[i]^=true;
//				flipped[k]^=true;
			}
			else if (type==3) {
				//swap
				int k=fs.nextInt();
				flipped[k+1]^=true;
//				flipped[k]^=true;
			}
			else if (type==4) {
				int l=fs.nextInt()-1, r=fs.nextInt()-1;
				long ans=st.rangeSum(l, r);
				out.println(ans);
			}
//			System.out.print(type+", Array now: ");
//			System.out.println(Arrays.toString(flipped));
//			System.out.println();
//			printArray(st, logn);
		}
		out.close();
	}
	
	static boolean[] flipped;
	
	static void printArray(SegTree st, int logn) {
		for (int i=0; i<1<<logn; i++) {
			System.out.print(st.rangeSum(i, i)+" ");
		}
		System.out.println();
	}
	
	static class SegTree {
		int leftmost, rightmost, level;
		long sum;
		SegTree[] kids=new SegTree[2];
		
		public SegTree(int leftmost, int rightmost, int level, int[] a) {
			this.leftmost=leftmost;
			this.rightmost=rightmost;
			this.level=level;
			if (leftmost!=rightmost) {
				int mid=(leftmost+rightmost)/2;
				kids[0]=new SegTree(leftmost, mid, level-1, a);
				kids[1]=new SegTree(mid+1, rightmost, level-1, a);
				recalc();
			}
			else {
				sum=a[leftmost];
			}
		}
		
		public void recalc() {
			sum=0;
			for (SegTree s:kids) sum+=s.sum;
		}
		
		public SegTree lChild() {
			if (flipped[level])
				return kids[1];
			return kids[0];
		}
		
		public SegTree rChild() {
			if (flipped[level])
				return kids[0];
			return kids[1];
		}
		
		public void pointUpdate(int index, int val) {
			if (leftmost==rightmost) {
				sum=val;
				return;
			}
			if (index<1<<(level-1)) {
				lChild().pointUpdate(index, val);
			}
			else {
				index-=(1<<(level-1));
				rChild().pointUpdate(index, val);
			}
			recalc();
		}
		
		public long rangeSum(int l, int r) {
			if (l<=0 && r>=(1<<level)-1) {
				return sum;
			}
			if (r<0 || l>=(1<<level)) return 0;
			long lSum=lChild().rangeSum(l, r);
			long rSum=rChild().rangeSum(l-(1<<(level-1)), r-(1<<(level-1)));
			return lSum+rSum;
		}
	}

	static final Random random=new Random();
	
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}

	
}
