Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hardest Update and Easiest Query

Limits: 2s, 128 MB

You have an array A with n elements which is indexed from 1 to n. Now you have to deal with two types of operations.

  1. Update i’th index of array A with value v. This is represented by the command ‘1 i v’. (1 <= i <= n) && (1 <= v <= 1000000000).

  2. Find the total sum of all possible pair (A[i] * A[j]) between L to R where L <= i < j <= R. This is represented by the command ‘2 L R’. (1 <= L <= R <= n).

Input

Input starts with an integer n (<=100000), denoting the number of elements of the array A. Next line contains n integers, the elements of the array A. Elements of array are in 1 to 1000000000. Third line contains an integer q, denoting the number of query (1 <= q <= 100000). Then next q lines contain any type of operations.

Output

Print the answer for each of the second type of operation with modulo 1000000007.

Samples

InputOutput
5
1 2 3 4 5
5
2 1 3
1 1 3
2 1 3
1 3 1
2 1 3
11
21
11

Discussion
Submit

Login to submit

Editorial

Login to unlock editorial