write a go solution for Description:
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 Format:
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,ldots,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 Format:
Print the answer for each Sum query.

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) to 8+8+7+1+5=29;
2. Reverse(1) to 0,7,8,8,1,7,2,5;
3. Swap(2) to 1,7,2,5,0,7,8,8;
4. Sum(1,6) to 1+7+2+5+0+7=22;
5. Reverse(3) to 8,8,7,0,5,2,7,1;
6. Replace(5,16) to 8,8,7,0,16,2,7,1;
7. Sum(8,8) to 1;
8. Swap(0) to 8,8,0,7,2,16,1,7.. Output only the code with no comments, explanation, or additional text.