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\)