Under construction

Still being built. Things may change

House Prices Going Up

Interview

Time limit1sMemory limit1024 MB

Summary
Given house prices, process updates that raise one house's price and queries that return the total price of houses l through r.
Level

Easy3 of 10

Topics
Array, Prefix sum
Solved
No attempts yet

Problem

The house prices in Virtual County (VC) keep going up. The Virtual County Tax Collection Agency needs help tracking the prices.

The houses in VC are numbered 1 through n, that is, 1, 2, 3, ..., n. VC records each price increase and wants the total price for any section of the county, for example the total for houses 4 through 15.

Input

The first line contains an integer n (1≤n≤5×1051 \le n \le 5 \times 10^5), the number of houses. Each of the next n lines contains an integer between 1 and 10910^9, inclusive, the initial price of one house. The first integer is the price of house 1, the second is the price of house 2, and so on.

The next line contains an integer t (1≤t≤1051 \le t \le 10^5), the number of transactions. Each of the next t lines is one of the following:

  • Update: a line starting with U, then a house number i, then an integer x (between 1 and 10910^9, inclusive). Increase the price of house i by x.
  • Retrieve: a line starting with R, then a starting house number l, then an ending house number r. Find the total price of houses l through r. The range is always valid, so r is not less than l.

Output

No output is required for Update transactions. For each Retrieve transaction, print the total price of the requested range on its own line.

Examples1

  1. Example 1

    Input
    5
100
200
150
300
250
8
R 2 4
U 2 20
U 3 40
R 2 4
R 1 5
U 2 10
U 4 100
R 1 5
    Expected output
    650
710
1060
1170