CF295E.Yaroslav and Points

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.

雅罗斯拉夫有 $n$ 个位于 $Ox$ 轴上的点。第一个点的坐标为 $x_1$，第二个点的坐标为 $x_2$，……，第 $n$ 个点的坐标为 $x_n$。现在雅罗斯拉夫希望执行 $m$ 个查询，每个查询属于以下两种类型之一：

1. 将第 $p_j$ 个点从位置 $x_{p_j}$ 移动到位置 $x_{p_j} + d_j$。注意：执行该查询后，所有点的坐标保证互不相同。
2. 计算所有位于区间 $[l_j,\, r_j]$（其中 $l_j \leq r_j$）内的点对之间的距离之和。换言之，需计算如下和式：
   。

请帮助雅罗斯拉夫完成上述任务。

The first line contains integer n — the number of points (1 ≤ n ≤ 105). The second line contains distinct integers _x_1, _x_2, ..., x__n — the coordinates of points (|x__i| ≤ 109).

The third line contains integer m — the number of queries (1 ≤ m ≤ 105). 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 ( - 109 ≤ l__j ≤ r__j ≤ 109).

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

第一行包含一个整数 $n$ —— 点的数量（$1 \leq n \leq 10^5$）。
第二行包含 $n$ 个互不相同的整数 $x_1, x_2, ..., x_n$ —— 各点的坐标（$|x_i| \leq 10^9$）。

第三行包含一个整数 $m$ —— 查询的数量（$1 \leq m \leq 10^5$）。
接下来的 $m$ 行为查询。第 $j$ 行首先包含一个整数 $t_j$（$1 \leq t_j \leq 2$）—— 查询类型。
若 $t_j = 1$，则其后跟两个整数 $p_j$ 和 $d_j$（$1 \leq p_j \leq n$, $|d_j| \leq 1000$）；
若 $t_j = 2$，则其后跟两个整数 $l_j$ 和 $r_j$（$-10^9 \leq l_j \leq r_j \leq 10^9$）。

保证在任意时刻所有点的坐标互不相同。

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.

对于每个类型 2 的查询，在单独一行输出答案。请按照输入中查询出现的顺序输出答案。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流或 %I64d 说明符。