F. House Prices Going Up
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The house prices have been going up and the Virtual County Tax Collection Agency needs help to keep track of prices.

We assume the houses in Virtual County (VC) are numbered $$$1$$$ through $$$n$$$, i.e., the house numbers are $$$1, 2, 3, ..., n$$$. VC keeps track of the house prices as they go up and would like to know the total price for different sections of the county, e.g., the total price for houses $$$4$$$ through $$$15$$$.

Input

The first input line contains an integer, $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$, indicating the number of houses in VC. Each of the next n input lines contains an integer (between $$$1$$$ and $$$10^9$$$, inclusive) indicating the initial price for a house; first integer is the price for the first house, second integer is the price for the second house, etc.

After the initial price information for all the houses, the input will have a set of transactions (operations) to be processed. This section of the input starts with an integer, $$$t$$$ $$$(1 \le t \le 10^5)$$$, indicating the number of transactions. Each of the next t input lines contains a transaction to be processed. There will be two types of transactions:

  • Update Transaction: This input line starts with the letter U in the first column, followed by one space, followed by a valid house number, followed by a space, followed by an integer (between $$$1$$$ and $$$10^9$$$, inclusive), indicating the increase in the price of that house.
  • Retrieve Transaction: This input line starts with the letter R in the first column, followed by one space, followed by a valid starting house number, followed by a space, followed by a valid ending house number. The total price for this range is being requested. Assume that the ending house number will not be less than the starting house number, i.e., the requested range is valid.
Output

There is no output required for Update transactions. For each Retrieve transaction, output a separate line providing the total price for the range being requested.

Example
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
Output
650
710
1060
1170