Given an array of $N$ integers and $Q$ queries. There are 2 types of queries: 1. $pos$ $val$ - set value at position $pos$ by $val$ (array is 1-indexed) 2. $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