You are given an array $A$ of $N$ integer elements.

You are also given $Q$ queries where each query is one of the following types:

• $1 i val$: Update value of element at i-th index to val i.e. A[i] = val
• $2 L R$: Find the value of function $\sum_\limits{i = L}^{R}\sum_\limits{j = i}^{R}\sum_\limits{k = i}^{j} A[k]$ .

Note: Assume 1-based indexing.

Input format

• The first line contains a single integer $T$ that denotes the number of test cases. 
• For each test case:
  • The first line contains an integer $N$.
  • The second line contains $N$ space-separated integers denoting array $A$.
  • The third line contains an integer $Q$.
  • Next $Q$ lines contain three space-separated integers denoting the queries.

Output format

For each test case, print the value of the function for queries of type 2 in the new line.

Constraints

$1 \le T \le 10 \\ 1 \le N \le 10^5 \\ 1 \le Q \le 10^3 \\ 1 \le A[i], val \le 10^6 \\ 1 \le i \le N \\ 1 \le L \le R \le N$