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\}. 
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

    def range(self, p, q):
        p += self.num-1
        q += self.num-2
        res = []
        while q-p>1:
            if p&1 == 0:
                res.append(p)
            if q&1 == 1:
                res.append(q)
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res.append(p)
        else:
            res.append(p)
            res.append(q)
        return res


import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = list(map(int, input().split()))
ss = SegTree(X,2**N,0,lambda x,y:x+y)
#print(ss.seg)
x = 0
for _ in range(Q):
    t = list(map(int, input().split()))
    if t[0] == 1:
#        print("update",(t[1]-1)^x)
        ss.update((t[1]-1)^x, t[2])
    elif t[0] == 2:
        x = x^((2**t[1])-1)
#        print("x",x)
    elif t[0] == 3:
        x = x^(2**t[1])
#        print("x",x)
    else:
        rr = ss.range(t[1]-1, t[2])
#        print(ss.query(t[1]-1, t[2]))
        R=0
        for r in rr:
            # r, seg[r] -> rの表す区間長(2**ll=2**(N-c+1))
            rt = r
#            print(r, ss.seg[r])
            c = 0
            while rt:
                rt=(rt-1)//2
                c+=1
            ll = N-c
            # rk : その区間長のもののうち幾つめ？
            rk=r-((1<<c)-1)
            m=x&(~((1<<ll)-1))
            m=m>>ll
#            print(rk, rk^m, m)
#            print(r, (rk^m)+((1<<c)-1), ss.seg[(rk^m)+((1<<c)-1)])

#            print(rk, r, ((1<<c)-1)+ rk^m)
#            print(rk,ll,m,(rk^m)+((1<<c)-1))
#            print(ss.seg[(rk^m)+((1<<c)-1)])
            R+=ss.seg[(rk^m)+((1<<c)-1)]
#        print(ss.seg)
#        print("ac",R)
        print(R)

