Hardest Update and Easiest Query

Comilla University CSE Fi...
Limits 2s, 512 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.

Sample

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

Submit

Login to submit.

Statistics

76% Solution Ratio
ssavi1994Earliest, Dec '17
AnachorFastest, 0.1s
AnachorLightest, 2.4 MB
AnachorShortest, 1395B
Toph uses cookies. By continuing you agree to our Cookie Policy.