Its time for the Potions class and Professor Snape is hell-bent on giving a detention to Harry. Today's class has a long table on which N elemental potions (numbered from 1 to N) are arranged. The queerness of the ith potion is A[i]. A unique bipotion can be obtained by mixing together small quantities of exactly two distinct elemental potions. Each unordered pair of distinct elemental potions corresponds to a different bipotion. The queerness of a bipotion is the product of the queernesses of the two elemental potions from which it was obtained.

Professor Snape performs Q actions during the course of the class. The ith action is specified by 3 integers, as follows :

0 q1 q2 : He replaces the potion at the q1'th position with a potion of queerness q2.
1 q1 q2 : He points to two potions q1 and q2 (st q1q2). In response to this, Harry must report the total queerness of all possible bipotions that can be obtained using the elemental potions numbered from q1 to q2 (inclusive).

Harry gets a detention if he answers any of the queries wrongly. You must help him to avoid getting one.

Input

The first line of input consists of a single integer N.
The second line contains N integers, A[1], A[2] .. A[N]. (Note that potions are allowed to have negative queerness.)
The third line contains a single integer Q.
Q lines follow. Each of these lines consists of 3 space-seperated integers : tp,q1,q2.

Output

Correctly formatted output consists of one line for each action with tp=1. Each of these lines must consist of a single integer: the number that Harry must report in response to that particular action.

Constraints

2N

-1000A[i]

1Q

0tp

if tp=0, 1q1N and -1000q2

if tp=1, 1q1q2N

Example

Input: 5 5 4 3 2 1 3 1 2 4 0 3 7 1 2 4 Output: 26 50

Explanation

The queerness sequence at the time of the first query is [5,4,3,2,1].
The queried section is [4,3,2].
2*3 + 3*4 + 2*4 = 6 + 12 + 8 = 26.
The queerness sequence at the time of the first query is [5,4,7,2,1].
The queried section is [4,7,2].
2*7 + 7*4 + 2*4 = 50.