RSQ Queries

Time limit: 2 secMemory limit: 256 MBData Structures, Math, Dynamic Programming

Problem Statement

Given an array of $N$ integers and $Q$ queries. There are 2 types of queries:

$pos$ $val$ - set value at position $pos$ by $val$ (array is 1-indexed)
$l$ $r$ - find sum on subsegment from $l$ to $r$
It is guaranteed that queries are valid.

Input Format

In first line of input is $N \leq 10^{5}$ . In the second line of input there are elements of array. $0 \leq elements \leq 10^{9}$ .
In the third line $Q \leq 10^{5}$ . In the next $Q$ lines there are queries.

Output Format

For each queries of second type print the sum.

Examples

Input

3
1 2 3
3
2 1 3
1 1 3
2 1 3

Output

6
8

Code Editor

Submit a solution. Authentication is required to create submissions.