Cho mảng \(A = (a_1, a_2, \ldots, a_n)\) chứa các số nguyên. Người ta thực hiện \(q\) truy vấn thuộc một trong \(3\) dạng sau:

• 1 u v: Tăng \(a_u\) lên \(v\) \((|v| \le 10^9)\)
• 2 u v: Gán \(a_u = v\) \((|v| \le 10^9)\)
• 3 u v: Tính tổng \(a_u + a_{u + 1} + \ldots + a_v\)

Input

• Dòng đầu là số nguyên dương \(n\) \((n \le 10^5)\).
• Dòng tiếp theo là \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((|a_i| \le 10^9)\).
• Dòng thứ ba là số nguyên dương \(m\) \((m \le 10^5)\).
• \(m\) dòng tiếp theo, mỗi dòng là một truy vấn nhập vào theo dạng trên.

Output

• Với các truy vấn loại \(3\) in ra kết quả trên một dòng.

5
1 2 3 4 5
6
1 4 3
2 2 3
3 2 4
1 5 2
2 4 -4
3 1 5

13
10