Pomekon Catalog
By Gabriel Duarte, UNIFESO 
Brazil
By Gabriel Duarte, UNIFESO Brazil
After capturing several Pokemons, Dabriel decided to separate them into different stacks and apply some operations on them. As you all know, Dabriel is a Pomekon Master, then your knowledge with programming are very limited, in that it has requested your help to solve his problem.
Dabriel want to perform Q operations on the stacks, each operation can be two types as described below:
1 X Y K: Returns the number of Pomekon that exist in the interval between X and Y positions after the K-th operation type 2. It is ensured that the K-th operation has already been made.
2 X W: Update the total of Pomekons on the X stack with the value W.
The input consists of several test cases. Each test case starts with an integer N (1 ≤ N ≤ 10⁵), representing the quantity of stacks. The second line will have N integers pi (1 ≤ pi ≤ 10⁵), representing how many Pomekons exist in the stack i.
On the next line will be an integer Q (1 ≤ Q ≤ 10⁵), which represents the amount of operations to be performed. Then follow Q lines, representing the Q operations.
The input ends with N = 0 and should not be processed.
For each operation of type 1, print a single line containing the amount of Pomekons that exist between X and Y stacks after the K-th operation.
| Input Samples | Output Samples |
|
4 |
3 |