#P1401F. Reverse and Swap

    ID: 1366 远端评测题 3000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbitmasksdata structures*2400

Reverse and Swap

Description

You are given an array aa of length 2n2^n. You should process qq queries on it. Each query has one of the following 44 types:

  1. Replace(x,k)Replace(x, k) — change axa_x to kk;
  2. Reverse(k)Reverse(k) — reverse each subarray [(i1)2k+1,i2k][(i-1) \cdot 2^k+1, i \cdot 2^k] for all ii (i1i \ge 1);
  3. Swap(k)Swap(k) — swap subarrays [(2i2)2k+1,(2i1)2k][(2i-2) \cdot 2^k+1, (2i-1) \cdot 2^k] and [(2i1)2k+1,2i2k][(2i-1) \cdot 2^k+1, 2i \cdot 2^k] for all ii (i1i \ge 1);
  4. Sum(l,r)Sum(l, r) — print the sum of the elements of subarray [l,r][l, r].

Write a program that can quickly process given queries.

The first line contains two integers nn, qq (0n180 \le n \le 18; 1q1051 \le q \le 10^5) — the length of array aa and the number of queries.

The second line contains 2n2^n integers a1,a2,,a2na_1, a_2, \ldots, a_{2^n} (0ai1090 \le a_i \le 10^9).

Next qq lines contains queries — one per line. Each query has one of 44 types:

  • "11 xx kk" (1x2n1 \le x \le 2^n; 0k1090 \le k \le 10^9) — Replace(x,k)Replace(x, k);
  • "22 kk" (0kn0 \le k \le n) — Reverse(k)Reverse(k);
  • "33 kk" (0k<n0 \le k < n) — Swap(k)Swap(k);
  • "44 ll rr" (1lr2n1 \le l \le r \le 2^n) — Sum(l,r)Sum(l, r).

It is guaranteed that there is at least one SumSum query.

Print the answer for each SumSum query.

Input

The first line contains two integers nn, qq (0n180 \le n \le 18; 1q1051 \le q \le 10^5) — the length of array aa and the number of queries.

The second line contains 2n2^n integers a1,a2,,a2na_1, a_2, \ldots, a_{2^n} (0ai1090 \le a_i \le 10^9).

Next qq lines contains queries — one per line. Each query has one of 44 types:

  • "11 xx kk" (1x2n1 \le x \le 2^n; 0k1090 \le k \le 10^9) — Replace(x,k)Replace(x, k);
  • "22 kk" (0kn0 \le k \le n) — Reverse(k)Reverse(k);
  • "33 kk" (0k<n0 \le k < n) — Swap(k)Swap(k);
  • "44 ll rr" (1lr2n1 \le l \le r \le 2^n) — Sum(l,r)Sum(l, r).

It is guaranteed that there is at least one SumSum query.

Output

Print the answer for each SumSum query.

Samples

样例输入 1

2 3
7 4 9 9
1 2 8
3 1
4 2 4

样例输出 1

24

样例输入 2

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

样例输出 2

29
22
1

Note

In the first sample, initially, the array aa is equal to {7,4,9,9}\{7,4,9,9\}.

After processing the first query. the array aa becomes {7,8,9,9}\{7,8,9,9\}.

After processing the second query, the array aia_i becomes {9,9,7,8}\{9,9,7,8\}

Therefore, the answer to the third query is 9+7+8=249+7+8=24.

In the second sample, initially, the array aa is equal to {7,0,8,8,7,1,5,2}\{7,0,8,8,7,1,5,2\}. What happens next is:

  1. Sum(3,7)Sum(3, 7) \to 8+8+7+1+5=298 + 8 + 7 + 1 + 5 = 29;
  2. Reverse(1)Reverse(1) \to {0,7,8,8,1,7,2,5}\{0,7,8,8,1,7,2,5\};
  3. Swap(2)Swap(2) \to {1,7,2,5,0,7,8,8}\{1,7,2,5,0,7,8,8\};
  4. Sum(1,6)Sum(1, 6) \to 1+7+2+5+0+7=221 + 7 + 2 + 5 + 0 + 7 = 22;
  5. Reverse(3)Reverse(3) \to {8,8,7,0,5,2,7,1}\{8,8,7,0,5,2,7,1\};
  6. Replace(5,16)Replace(5, 16) \to {8,8,7,0,16,2,7,1}\{8,8,7,0,16,2,7,1\};
  7. Sum(8,8)Sum(8, 8) \to 11;
  8. Swap(0)Swap(0) \to {8,8,0,7,2,16,1,7}\{8,8,0,7,2,16,1,7\}.