Description
You are given an array a of length 2n. You should process q queries on it. Each query has one of the following 4 types:
- Replace(x,k) — change ax to k;
- Reverse(k) — reverse each subarray [(i−1)⋅2k+1,i⋅2k] for all i (i≥1);
- Swap(k) — swap subarrays [(2i−2)⋅2k+1,(2i−1)⋅2k] and [(2i−1)⋅2k+1,2i⋅2k] for all i (i≥1);
- Sum(l,r) — print the sum of the elements of subarray [l,r].
Write a program that can quickly process given queries.
The first line contains two integers n, q (0≤n≤18; 1≤q≤105) — the length of array a and the number of queries.
The second line contains 2n integers a1,a2,…,a2n (0≤ai≤109).
Next q lines contains queries — one per line. Each query has one of 4 types:
- "1 x k" (1≤x≤2n; 0≤k≤109) — Replace(x,k);
- "2 k" (0≤k≤n) — Reverse(k);
- "3 k" (0≤k<n) — Swap(k);
- "4 l r" (1≤l≤r≤2n) — Sum(l,r).
It is guaranteed that there is at least one Sum query.
Print the answer for each Sum query.
The first line contains two integers n, q (0≤n≤18; 1≤q≤105) — the length of array a and the number of queries.
The second line contains 2n integers a1,a2,…,a2n (0≤ai≤109).
Next q lines contains queries — one per line. Each query has one of 4 types:
- "1 x k" (1≤x≤2n; 0≤k≤109) — Replace(x,k);
- "2 k" (0≤k≤n) — Reverse(k);
- "3 k" (0≤k<n) — Swap(k);
- "4 l r" (1≤l≤r≤2n) — Sum(l,r).
It is guaranteed that there is at least one Sum query.
Output
Print the answer for each Sum query.
Samples
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 ai 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:
- Sum(3,7) → 8+8+7+1+5=29;
- Reverse(1) → {0,7,8,8,1,7,2,5};
- Swap(2) → {1,7,2,5,0,7,8,8};
- Sum(1,6) → 1+7+2+5+0+7=22;
- Reverse(3) → {8,8,7,0,5,2,7,1};
- Replace(5,16) → {8,8,7,0,16,2,7,1};
- Sum(8,8) → 1;
- Swap(0) → {8,8,0,7,2,16,1,7}.