fenwicktree_easy

Potato has N blåhajar (plural of blåhaj). Initially, the ith blåhaj has an age of Ai.

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 < xyN. You are to respond with the sum of the ages of the blåhajar between the xth blåhaj and the yth blåhaj inclusive.

For each update, Potato will provide you with two integers, a, b. This means that the ath 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, -106 ≤ Ai ≤ 106, 0 < x ≤ y ≤ N, 0 < a ≤ N, -106 ≤ b ≤ 106

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 xth blåhaj and the yth 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

Submitting to 'fenwicktree_easy'


You're not logged in! Click here to login


Submitting to 'fenwicktree_easy'


You're not logged in! Click here to login


Submitting .cpp to 'fenwicktree_easy'


You're not logged in! Click here to login

Time Limit: 1 Seconds
Memory Limit: 1024MB
Your best score: 0
Source: RI November Course 2023 Diagnostic Test (Potato3218, nianhe)

Subtask Score
1 42
2 58
3 0