LGLOVE - LCM GCD Love

no tags 

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

hide comments
maikelele: 2020-05-07 08:28:05

Can anyone explain this part, "Output one line for each query of type 1 or 2, modulo 1000000007." ??

Sigma Kappa: 2018-06-14 01:14:38

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
Jaswanth: 2015-09-06 04:32:49

@Prof_Utonium_ಉಮೆಶ್: can u tell where my solution is going wrong. submission id=15069964

californiagurl: 2014-12-22 18:57:36

anybody else getting SIGSEGV? :/

Damian Straszak: 2012-05-27 11:55:18

the outputs are incorrect, only a wrong solution can pass
For example for GCD(1,0,6,60) you should output... 0.

Walrus: 2012-02-06 08:02:27

and gcd(0,i) = 0 or i?
similarly, lcm(0,i)= 0 or i?

Ehor Nechiporenko: 2010-10-07 16:30:54

0 0

ymGXX: 2010-10-07 03:55:11

gcd(0,0)=?
lcm(0,0)=?


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