Cho một dãy $A_1, A_2, \ldots, A_N$ độ dài $N$. Hãy viết chương trình xử lý các truy vấn sau:

• 1 i v: Gán $A_i$ bằng $v$.
• 2 k i j: Khi truy vấn loại 1 thứ $k$ đã được thực hiện, hãy xuất ra tổng của $A_i, A_{i+1}, \ldots, A_j$.

Dữ liệu vào

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

Dòng thứ hai chứa $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 1{,}000{,}000$).

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. Với truy vấn loại 1, $1 \le i \le N$, $1 \le v \le 1{,}000{,}000$; với truy vấn loại 2, $1 \le i \le j \le N$, và $0 \le k \le$ (số lượng truy vấn loại 1 đã xuất hiện cho đến thời điểm đó).

Tất cả các số trong đầu vào đều là số nguyên.

Dữ liệu ra

Với mỗi truy vấn loại 2, hãy in ra tổng tương ứng.

Ví dụ

Đầu vào 1

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

Đầu ra 1

6
9
14
17
15