Yaroslav has $*n*$ points that lie on the $*Ox*$ axis. The coordinate of the first point is $*x*_{1}$, the coordinate of the second point is $*x*_{2}$, ..., the coordinate of the $*n*$-th point is — $*x*_{*n*}$. Now Yaroslav wants to execute $*m*$ queries, each of them is of one of the two following types:

1. Move the $*p*_{*j*}$-th point from position $*x*_{*p*_{*j*}}$ to position $*x*_{*p*_{*j*}} + *d*_{*j*}$. At that, it is guaranteed that after executing such query all coordinates of the points will be distinct.
2. Count the sum of distances between all pairs of points that lie on the segment $[*l*_{*j*}, *r*_{*j*}]$ $(*l*_{*j*} ≤ *r*_{*j*})$. In other words, you should count the sum of: .

Help Yaroslav.

Input

The first line contains integer $*n*$ — the number of points $(1 ≤ *n* ≤ 10^{5})$. The second line contains distinct integers $*x*_{1}, *x*_{2}, ..., *x*_{*n*}$ — the coordinates of points $(|*x*_{*i*}| ≤ 10^{9})$.

The third line contains integer $*m*$ — the number of queries $(1 ≤ *m* ≤ 10^{5})$. The next $*m*$ lines contain the queries. The $*j*$-th line first contains integer $*t*_{*j*}$ $(1 ≤ *t*_{*j*} ≤ 2)$ — the query type. If $*t*_{*j*} = 1$, then it is followed by two integers $*p*_{*j*}$ and $*d*_{*j*}$ $(1 ≤ *p*_{*j*} ≤ *n*, |*d*_{*j*}| ≤ 1000)$. If $*t*_{*j*} = 2$, then it is followed by two integers $*l*_{*j*}$ and $*r*_{*j*}$ $( - 10^{9} ≤ *l*_{*j*} ≤ *r*_{*j*} ≤ 10^{9})$.

It is guaranteed that at any moment all the points have distinct coordinates.

Output

For each type 2 query print the answer on a single line. Print the answers in the order, in which the queries follow in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams of the %I64d specifier.