Humanity has finally discovered the planet Yanaizu, which is home to intelligent life. As science progressed on Yanaiizu, collaboration with us gradually became more and more active.
On the planet Yanaizu, an insect called Beko is considered to be an important resource. It grows from a larva to an adult. In their habitat, there are several colonies of Beko larvae living in swarms, and these colonies are arranged in a row. Using the biotechnology of the planet Yanaizu, the following operations can be performed on the swarms.
In the second operation, if the number of larvae in a group is less than the specified number, all the larvae in that group are hatched. For example, if there are three larvae in group 1 and two larvae in group 2, and the number of larvae to be hatched in groups 1 to 2 is 3, then three larvae from group 1 and two larvae from group 2 will be hatched into adults. In this case, the total number of larvae hatched is five.
In this collaborative research, we humans were in charge of simulating these operations on Beko larvae. This is the time to show the power of our science.
Given the information about the larvae in each swarms, write a program to simulate the operations on them.
The input is given in the following form.
$N$ $c_1$ $c_2$ : $c_N$ $M$ $manip_1$ $manip_2$ : $manip_M$
In the first line, the number of swarms $N$ ($1 \leq N \leq 100,000$) is given. In the following $N$ lines, the number of larvae in each swarm $c_i$ ($0 \leq c_i \leq 100,000$) is given.
In the next line, the number of operations $M$ ($1 \leq M \leq 100,000$) is given. In the following $M$ lines, the contents of the operations are given. The content of each operation is one of the following:
1 $a$ $b$ $d$
or
2 $a$ $b$ $d$
If the first number is 1, add $d$ larvae ($1 \leq d \leq 1,000$) to the swarm in the specified range $a$ to $b$ ($1 \leq a \leq b \leq N$). When the first number is 2, it represents the operation to hatch $d$ larvae ($1 \leq d \leq 1,000$) into adults in all the swarms in the range $a$ to $b$ ($1 \leq a \leq b \leq N$). In this case, the total number of larvae actually hatched should be output. It is assumed that at least one operation with a leading number of 2 is always given.
Output the total number of larvae actually hatched in a line for each operation that hatches larvae.
3 1 2 3 3 2 1 3 2 1 1 2 5 2 2 3 3
5 4