Cho một dãy $A_0, A_1, \ldots, A_{N-1}$ độ dài $N$. Hãy viết chương trình xử lý các truy vấn sau ($0 \le A_i < 2^{32}$):

• 1 p v: Chèn $v$ vào trước $A_p$. Nếu $p$ bằng độ dài của $A$, nó được chèn ở cuối. ($0 \le p \le$ độ dài của $A$, $0 \le v < 2^{32}$)
• 2 p: Xóa $A_p$. ($0 \le p <$ độ dài của $A$)
• 3 p v: Thay đổi $A_p$ thành $v$. ($0 \le p <$ độ dài của $A$, $0 \le v < 2^{32}$)
• 4 l r k: Tính $(\sum A_i \times (i - l + 1)^k) \bmod 2^{32}$ và in ra. ($0 \le k \le 10$)

Dữ liệu vào

Dòng đầu tiên chứa độ dài của dãy $N$ ($1 \le N \le 100{,}000$).

Dòng thứ hai chứa $A_0, A_1, \ldots, A_{N-1}$.

Dòng thứ ba chứa số lượng truy vấn $M$ ($1 \le M \le 100{,}000$).

$M$ dòng tiếp theo, mỗi dòng chứa một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra câu trả lời trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

4
1 2 3 5
7
4 0 2 0
1 3 4
4 2 4 1
2 0
4 0 3 1
3 1 2
4 0 1 0

Dữ liệu ra 1

6
26
40
4