Akash is interested in a new function F such that,
F(x)=1GCD(1,x)+2GCD(2,x)+...+xGCD(x,x)
where GCD is the Greatest Common Divisor.
Now, the problem is quite simple. Given an array A of size N, there are 2 types of queries:
- C X Y : Compute the value of F(A[X])+F(A[X+1])+F(A[X+2])+....+F(A[Y]) (mod109+7)
- U X Y: Update the element of array A[X]=Y
Input:
First line of input contain integer N, size of the array.
Next line contain N space separated integers.
Next line contain integer Q, number of queries.
Next Q lines contain one of the two queries.
Output:
For each of the first type of query, output the required sum (mod 109+7).
Constraints:
1≤N≤106
1≤Q≤105
1≤A[i]≤5∗105
For 1st type of query,
1≤X≤Y≤N
For 2nd type of query
1≤X≤N
1≤Y≤5∗105
A[1]=3,A[2]=4,A[3]=3
F(3)=1GCD(1,3)+2GCD(2,3)+3GCD(3,3)=1+2+1=4
F(4)=1GCD(1,4)+2GCD(2,4)+3GCD(3,4)+4GCD(4,4)=1+1+3+1=6.
First query, the sum will be F(3)+F(4)=4+6=10(mod109+7).
Second query, the sum will be F(3)+F(4)+F(3)=4+6+4=14(mod109+7).
Third query, the sum will be F(3)=4(mod109+7).
Fourth query will update A[1]=4.
Fifth query, the sum will be F(4)+F(4)+F(3)=6+6+4=16(mod109+7).
Sixth query, the sum will be F(4)+F(4)=6+6=12(mod109+7).
