LGLOVE - LCM GCD Love

Bob fell in love with LCM and GCD. So much that he started seeing LCMs and GCDs everywhere. Betty, his girlfriend 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

Added by:Prof_Utonium_ಉಮೆಶ್
Date:2010-10-05
Time limit:0.108s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-RHINO OBJC SQLITE
Resource:MNNIT IOPC 2010 , Co-author: ashish_pant

hide comments
2020-05-07 08:28:05
Can anyone explain this part, "Output one line for each query of type 1 or 2, modulo 1000000007." ??
2018-06-14 01:14:38 Sigma Kappa
When pre-computing all the LCMs, do we make use of recurrence lcm[x] = lcm[x-1]*x*modular_inverse(gcd(lcm[x-1],x)) % MOD?

Last edit: 2018-06-18 22:05:48
2015-09-06 04:32:49 Jaswanth
@Prof_Utonium_ಉಮೆಶ್: can u tell where my solution is going wrong. submission id=15069964
2014-12-22 18:57:36 californiagurl
anybody else getting SIGSEGV? :/
2012-05-27 11:55:18 Damian Straszak
the outputs are incorrect, only a wrong solution can pass
For example for GCD(1,0,6,60) you should output... 0.
2012-02-06 08:02:27 Walrus
and gcd(0,i) = 0 or i?
similarly, lcm(0,i)= 0 or i?
2010-10-07 16:30:54 Ehor Nechiporenko
0 0
2010-10-07 03:55:11 ymGXX
gcd(0,0)=?
lcm(0,0)=?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.