LCM GCD Love
Bob fell in love with LCM and GCD. So much that he started seeing LCMs and GCDs everywhere.
Betty, his girl friend was jealous and she gave Bob an array A[ ] of integers, which had nothing to do with LCMs or GCDs.
Quickly, naughty Bob evaluated a new array B[ ] containing n integers, such that B[i] is LCM(1,2,3,...,A[i]), A[i]>0. When A[i] is 0, B[i] is also 0.
Angry Betty decided to give m queries to Bob, each being one of the following type:
- "0 i j p", meaning add 'p' to each element in A[i..j]. -300000<= p <= 300000 , 0<=i<=j<n
- "1 i j" , meaning print the LCM of all elements in B[i..j]. 0<=i<=j<n
- "2 i j" , meaning print the GCD of all elements in B[i..j].0<=i<=j<n
Input
First line contains n(n <= 100000 ) and m( m <= 35000 ).
Second line contains n integers in the original array A[ ] .
Next m lines contain one of the above said queries.
It is guaranteed that A[i] after any number of updates will satisfy 0<=A[i]<=300000.
Output
Output one line for each query of type 1 or 2, modulo 1000000007.
Example
Input:5 5
4 1 3 6 2
1 2 4
2 1 3
0 0 3 2
1 1 2
2 2 4
Output:
60
1
60
2