shil-and-oblivion-treasure-12

While diving in ancient river of Egypt, Shil came across an oblivion treasure of algorithms and data structures.This treasure has powerful algorithmic lock.The procedure to open the lock is as follows:
Given N natural numbers A1, A2, A3 . . .  AN, you have process Q queries of following two types:
1 i j: Perform the operation Ai = j.
2 L R: Print the LCM of the elements AL, AL+1, AL+2 . . .  AR.
Here LCM stands for lowest common multiple. Please help Shil to open the lock.

Input
First line will contain integer N.
Second line will contain N natural numbers denoting array A. 
Third line will contain number of queries Q. 
Then next Q lines will contain either query of Type 1 or 2.   

Output 
For each query of Type 2 output the required answer.
Since LCM can be very large output it modulus 10^9+7.

Constraints 
1 ≤ N ≤ 10^4
1 ≤ Ai ≤ 1000 
  1 ≤ Q ≤ 10^4
1 ≤ L ≤ R ≤ N
1 ≤ i ≤ N
1 ≤ j ≤ 1000

SAMPLE INPUT
6
1 3 2 5 10 3
5
2 2 3
1 5 5
2 4 5
2 4 6
2 2 2SAMPLE OUTPUT
6
5
15
3Explanation

In above Sample Case, there are 5 queries.
 In First query , you have to calculate LCM of a[2] and a[3] and output its value i.e. 6
 In Second query , you have to update a[5] to 5 
 In Third query , you have to calculate LCM of a[4] and a[5] and output its value .i.e 5

Source: hackerearth | Difficulty: MEDIUM


Solutions: