URI Online Judge | 2223

Pomekon Catalog

By Gabriel Duarte, UNIFESO BR Brazil

Timelimit: 1

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.

Input

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.

Output

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
1 2 3 4
9
1 1 2 0
1 1 3 0
1 1 4 0
2 1 5
1 1 4 1
1 1 1 1
2 4 0
1 1 4 0
1 1 4 2
0

3
6
10
14
5
10
10