Đảo và hoán đổi

Cho mảng $a$ có độ dài $2^n$. Bạn cần xử lý $q$ truy vấn, mỗi truy vấn thuộc một trong bốn loại sau:

1. Replace$(x,k)$ — gán $a_x:=k$.
2. Reverse$(k)$ — với mỗi $i\ge 1$, đảo ngược đoạn con $[(i-1)·2^k+1,i·2^k]$.
3. Swap$(k)$ — với mỗi $i\ge 1$, hoán đổi hai đoạn con liền kề $[(2i-2)·2^k+1,(2i-1)·2^k]$ và $[(2i-1)·2^k+1,2i·2^k]$.
4. Sum$(l,r)$ — in ra tổng các phần tử của đoạn $[l,r]$.

Hãy viết chương trình xử lý các truy vấn cho trước một cách hiệu quả.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n,q$ — chiều dài luỹ thừa $2$ của mảng và số truy vấn.
• Dòng thứ hai chứa $2^n$ số nguyên $a_1,a_2,\dots ,a_{2^n}$.
• $q$ dòng tiếp theo mỗi dòng mô tả một truy vấn theo một trong các định dạng:
  • "1 $x$ $k$" — Replace$(x,k)$, với $1\le x\le 2^n$, $0\le k\le {10}^9$.
  • "2 $k$" — Reverse$(k)$, với $0\le k\le n$.
  • "3 $k$" — Swap$(k)$, với $0\le k<n$.
  • "4 $l$ $r$" — Sum$(l,r)$, với $1\le l\le r\le 2^n$.

Bảo đảm có ít nhất một truy vấn loại 4.

Dữ liệu ra

In ra đáp án của mỗi truy vấn Sum, mỗi đáp án trên một dòng riêng.

Ràng buộc

• $0\le n\le 18$
• $1\le q\le {10}^5$
• $0\le a_i\le {10}^9$

Ví dụ