You have an array of N problems A. Each problem has a difficulty level. i-th problem has dificulty A[i].

You want to give these problems to HrSiam. But you know, HrSiam doesn't like easy problems, so he will get angry. Also he doesn't want to solve problems with same difficulty again and again.

So he also has an array angry, with N elements.

When he visits a problem with certain difficulty d, his angriness will increase by d * angry[1].
After some time if he again visits a problem with same difficulty for the second time, then his angriness will increase by d * angry[2], and so on.
Generally, if he visit a problem with certain difficulty d for the i-th time, his angriness will increase by d * angry[i].

In this circumstances, you want to do 2 things -
1. You are afraid that HrSiam may get too angry, so you want to present a part of the array to him. But you need to quickly determine: what will be his total angriness if you present the sub array of problems A[l...r] to HrSiam?
2. After certain time you may want to change difficulty of a problem, i.e set difficulty of x-th problem to y.

Input

First line there will an integer N, the number of problems you have.

Next line will contain the difficulty of the problems, the array A[]. 

Next line will contain the array angry[], of length N.

Next line, there will be an integer Q, the number of queries you want to make.

Next Q lines will describe the queries, in format -

t x y

If t is one, then you need to find the total angriness of the Subarray A[l...r] when presented to HrSiam.
Else you need to set A[x] = y.

Constraints

1 <= N, Q, x, y, A[i], angry[i] <= 100000 

If x, y is in query of first type, then 1 <= x <= y <= N                                                                                                                                             

Output

For each query of first type, print an integer: the total angriness of the subarray. Solutions to the queries should be printed in the order they appeared in the input.

Explanation of Sample

In the first sample, the first query range is [3, 6], the array elements are {3, 3, 1, 1}.
When HrSiam see the first problem with difficulty 3, his angriness will increase by 3 * angry[1].
Then he visit a problem with same difficulty he saw before, for the second time, so add 3 * angry[2]
Then 1 * angry[1] and 1 * angry[2]
Total = (3 * 1) + (3 * 2) + (1 * 1) + (1 * 2) = 12

Example

Input:
8
1 2 3 3 1 1 2 3 
1 2 3 4 5 6 7 8
2
1 3 6 
1 1 5 

Output:
12
14