Yaroslav has n points that lie on the Ox axis. The coordinate of the first point is x1, the coordinate of the second point is x2, ..., the coordinate of the n-th point is — xn. Now Yaroslav wants to execute m queries, each of them is of one of the two following types:

  1. Move the pj-th point from position xpj to position xpj + dj. 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 [lj, rj] (lj ≤ rj). In other words, you should count the sum of: <image>. 



Help Yaroslav.

Input

The first line contains integer n — the number of points (1 ≤ n ≤ 105). The second line contains distinct integers x1, x2, ..., xn — the coordinates of points (|xi| ≤ 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 tj (1 ≤ tj ≤ 2) — the query type. If tj = 1, then it is followed by two integers pj and dj (1 ≤ pj ≤ n, |dj| ≤ 1000). If tj = 2, then it is followed by two integers lj and rj ( - 109 ≤ lj ≤ rj ≤ 109).

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.

Examples

Input

8
36 50 28 -75 40 -60 -95 -48
20
2 -61 29
1 5 -53
1 1 429
1 5 130
2 -101 -71
2 -69 53
1 1 404
1 5 518
2 -101 53
2 50 872
1 1 -207
2 -99 -40
1 7 -389
1 6 -171
1 2 464
1 7 -707
1 1 -730
1 1 560
2 635 644
1 7 -677


Output

176
20
406
1046
1638
156
0
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.math.*;
import java.awt.geom.*;

import static java.lang.Math.*;

public class Solution implements Runnable {
	
	void randomShuffle (long a[]) {
		Random rnd = new Random();
		for (int i = 1; i < a.length; i++) {
			int j = rnd.nextInt(i + 1);
			long t = a[i];
			a[i] = a[j];
			a[j] = t;
		}
	}
	
	public void solve() throws Throwable {
		int n = sc.nextInt();
		long a [] = new long [n];
		long point [] = new long [n];
		for (int i = 0; i < n; i++) {
			a[i] = point[i] = sc.nextInt();
		}
		randomShuffle(a);
		Arrays.sort(a);
		Treap root = null;
		for (int i = 0; i < n; i++) {
			root = Treap.merge(root, new Treap(a[i]));
		}
		int m = sc.nextInt();
		for (int i = 0; i < m; i++) {
			int type = sc.nextInt();
			if (type == 1) {
				int index = sc.nextInt() - 1;
				int d = sc.nextInt();
				Treap left [] = Treap.split(root, point[index]);
				Treap right [] = Treap.split(left[1], point[index] + 1);
				root = Treap.merge(left[0], right[1]);
				point[index] += d;
				left = Treap.split(root, point[index]);
				right = Treap.split(left[1], point[index] + 1);
				root = Treap.merge(left[0], new Treap(point[index]));
				root = Treap.merge(root, right[1]);
			} else {
				int l = sc.nextInt();
				int r = sc.nextInt();
				Treap left [] = Treap.split(root, l);
				Treap right [] = Treap.split(left[1], r + 1);
				out.println(Treap.getPairSum(right[0]));
				root = Treap.merge(left[0], right[0]);
				root = Treap.merge(root, right[1]);
			}
		}
	}

	BufferedReader in;
	PrintWriter out;
	FastScanner sc;

	static Throwable uncaught;

	@Override
	public void run() {
		try {
			in = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
			sc = new FastScanner(in);
			solve();
		} catch (Throwable t) {
			Solution.uncaught = t;
		} finally {
			out.close();
		}
	}

	public static void main(String[] args) throws Throwable {
		Thread t = new Thread(null, new Solution(), "", (1 << 26));
		t.start();
		t.join();
		if (uncaught != null) {
			throw uncaught;
		}
	}

}

class FastScanner {

	BufferedReader reader;
	StringTokenizer strTok;

	public FastScanner(BufferedReader reader) {
		this.reader = reader;
	}

	public String nextToken() throws IOException {
		while (strTok == null || !strTok.hasMoreTokens()) {
			strTok = new StringTokenizer(reader.readLine().trim());
		}
		return strTok.nextToken();
	}

	public int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	public long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	public double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

}

class Treap {
	
	static Random rnd = new Random();
	
	long x, sum, pairSum;
	int prior, cnt;
	Treap l, r;
	
	public Treap(long x) {
		this.x = x;
		this.sum = x;
		this.pairSum = 0;
		this.cnt = 1;
		this.prior = rnd.nextInt();
	}
	
	public static long getSum (Treap t) {
		return t == null ? 0 : t.sum;
	}
	
	public static long getPairSum (Treap t) {
		return t == null ? 0 : t.pairSum;
	}
	
	public static int getCount (Treap t) {
		return t == null ? 0 : t.cnt;
	}
	
	public static void updateVertex (Treap t) {
		if (t == null) return;
		t.cnt = getCount(t.l) + getCount(t.r) + 1;
		t.sum = getSum(t.l) + getSum(t.r) + t.x;
		t.pairSum = getPairSum(t.l) + getPairSum(t.r);
		if (t.l != null)
			t.pairSum += t.x * getCount(t.l) - getSum(t.l);
		if (t.r != null)
			t.pairSum += getSum(t.r) - t.x * getCount(t.r);
		if (t.l != null && t.r != null)
			t.pairSum += getSum(t.r) * getCount(t.l) - getSum(t.l) * getCount(t.r);
	}
	
	public static Treap merge (Treap l, Treap r) {
		if (l == null) return r;
		if (r == null) return l;
		if (l.prior > r.prior) {
			l.r = merge (l.r, r);
			updateVertex(l);
			return l;
		} else {
			r.l = merge (l, r.l);
			updateVertex(r);
			return r;
		}
	}
	
	public static Treap [] split (Treap t, long key) {
		if (t == null) return new Treap [] {null, null};
		Treap[] res = null;
		if (key <= t.x) {
			res = split (t.l, key);
			t.l = res[1];
			res[1] = t;
		} else {
			res = split (t.r, key);
			t.r = res[0];
			res[0] = t;
		}
		updateVertex(res[0]);
		updateVertex(res[1]);
		return res;
	}
	
	public static void dfs (Treap t, StringBuilder sb) {
		if (t == null) return;
		dfs (t.l, sb);
		sb.append(t.x);
		sb.append(" ");
		dfs (t.r, sb);
	}
	
}