Mr. Fenwick has an array a with many integers, and his children love to do operations on the array with their father. The operations can be a query or an update.

For each query the children say two indices l and r, and their father answers back with the sum of the elements from indices l to r (both included).

When there is an update, the children say an index i and a value x, and Fenwick will add x to a_i (so the new value of a_i is a_i + x).

Because indexing the array from zero is too obscure for children, all indices start from 1. Fenwick is now too busy to play games, so he needs your help with a program that plays with his children for him, and he gave you an input/output specification.

Input

The first line of the input contains N (1 ≤ N ≤ 10⁶). The second line contains N integers a_i (−10⁹ ≤ a_i ≤ 10⁹), the initial values of the array. The third line contains Q (1 ≤ Q ≤ 3 × 10⁵), the number of operations that will be made. Each of the next Q lines contains an operation. Query operations are of the form “q l r” (1 ≤ l ≤ r ≤ N), while update operations are of the form “u i x” (1 ≤ i ≤ N, −10⁹ ≤ x ≤ 10⁹).

Output

You have to print the answer for every query in a different line, in the same order of the input.

Example

Input:
10
3 2 4 0 42 33 -1 -2 4 4
6
q 3 5
q 1 10
u 5 -2
q 3 5
u 6 7
q 4 7

Output:
46
89
44
79