candies-condition

Students of IIITM love candies. There are N students in IIITM. They are standing in a line from Left to Right at Positions(1 to N). Dr. Niru decided to pick consecutive students from the line and give them candies. Now each student wish to have some number of candies A[i]. And they will take candies from Dr. Niru only if he has number of candies that is a multiple of A[i]. Now Dr. Niru wants that each student from his picked students should get the candies. So he wants to know the minimum number of candies he should have when he picks the students. Also at any particular time the students can wish for more or less number of candies. So Dr. Niru has to take that into account.

Please help Dr. Niru to select the minimum number of candies.

Input

The input file consists of several cases T (1 ≤ T ≤ 5). 
The first line of each case contains a positive integer N (1 ≤ N ≤ 16384) specifying the number of students in IIITM.  In next line there are N space separated values A[i..n] (1 ≤ A[i] ≤ 1000) which is the number of candies that student I wants. I is 1-Indexed.
In Next line there is Q i.e number of queries [1 ≤ Q ≤ 1000]. Queries are of two types –
1. 0 a b -> It means update the the number of candies that student a wants to b.
2. 1 a b -> Tell the minimum number of candies that Dr. Niru should have to satisfy the students from [a,b].

Output

For every query of the form 1 a b, you have to print the answer  modulo 1000000007 in a separate line.

SAMPLE INPUT
1
2
2 4
3
1 1 2
0 1 3
1 1 2

SAMPLE OUTPUT
4
12

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: