Cho một dãy số n phần tử ~ a_1, a_2, ..., a_n ~ và một số các truy vấn. Một truy vấn là một bộ ba (type, i, j) (0 ≤type ≤ 1, 1 ≤ i ≤ j ≤ n).

Với mỗi truy vấn (type, i, j):

• Nếu type = 1 : Tính tổng đoạn ~ a_i + a_{i+1} + ... + a_j~
• Nếu type = 0 : Tăng giá trị a[i] thêm j.

Input

Dòng 1: n ~(1 ≤ n ≤ 10^6).~

Dòng 2: n số ~ a_1, a_2, ..., a_n (1 ≤ a_i ≤ 1000).~

Dòng 3: q (1 ≤ q ≤ 200000), số lượng truy vấn.

Trong q dòng sau, mỗi dòng chứa 3 số type, i, j biểu thị một truy vấn (0 ≤type ≤ 1, 1 ≤ i ≤ j ≤ n).

Kết quả

Với mỗi truy vấn (type, i, j):

• Nếu type = 1 : In ra tổng đoạn ~ a_i + a_{i+1} + ... + a_j~ trên 1 dòng.
• Nếu type = 0 : Tăng giá trị a[i] thêm j.

Sample Input

10
20 1 1 1 1 10 1 1 1 1
5
1 1 1
1 1 10
1 5 10
0 6 5
1 5 10

Sample Output

20
38
15
20