fenwicktree_easy

Potato has N blåhajar (plural of blåhaj). Initially, the i^th blåhaj has an age of A_i.

Sometimes, due to magic, some blåhajar can change their age! As such, Potato wants you to answer queries and updates about the ages of the blåhajar. In total, there will be M queries and updates. All updates are guaranteed to be before all the queries.

For each query, Potato will provide you with two integers x and y where 0 < x ≤ y ≤ N. You are to respond with the sum of the ages of the blåhajar between the x^th blåhaj and the y^th blåhaj inclusive.

For each update, Potato will provide you with two integers, a, b. This means that the a^th blåhaj has changed its age to b.

Note

As this problem deals with large inputs and outputs, you are strongly advised to insert these 2 lines of code at the start of your main() function:

ios_base::sync_with_stdio(false);

cin.tie(NULL);

Limits

For all testcases, -10⁶ ≤ A_i ≤ 10⁶, 0 < x ≤ y ≤ N, 0 < a ≤ N, -10⁶ ≤ b ≤ 10⁶

Subtask 1 (42%): 1 ≤ N ≤ 100, 0 ≤ M ≤ 200.

Subtask 2 (58%): 1 ≤ N ≤ 1000000, 0 ≤ M ≤ 1000000.

Subtask 3 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain N integers, representing the respective ages of the N blåhajar.

The next line will contain a single integer, M.

M lines will follow. The first character of each line will be T.

If T is 0, then it represents a query. 2 integers will then follow, x and y.

If T is 1, then it represents an update. 2 integers will then follow, a and b.

Output

For each line of query, you are to output the sum of the ages of the blåhajar between the x^th blåhaj and the y^th blåhaj inclusive, on a single line.

Sample Testcase 1

Input

10
1 2 9 5 7 6 3 4 2 2
5
1 1 8
0 1 2
0 6 10
0 1 9
0 5 7

Output

10
17
46
16