Zadanie

Kráľova nová daň

Počet bodov: 90

Kráľ Maximilián Stredný nedávno bez rozmyslu podpísal návrh jeho poradcu o novej dani na príjmy z čarodejníckej činnosti a nových obmedzení týkajúcich sa magických odvarov.

To nebol jeho najšťastnejší deň, lebo za odplatu mu Čarodejnica Matematica zakliala jeho jedinú dcéru, Princeznú Janku.

Matematicina kliatba je veľmi zákerná, lebo jej vyčarovanie je určené postupnosťou \(n\) čísel, s ktorými Matematica spravila niekoľko operácií.

Napriek sľubom že dane sa v budúcnosti znížia sa Matematica už odsťahovala do kráľovstva s lepšími daňovými podmienkami.

Je teda na Kúzelníkovi Kubíkovi, aby Janku odčaroval. Ten si práve povzdychol, lebo si na pergamene s kliatbou práve prečítal

Označme LCM(x) najmenší spoločný násobok čísel 1, 2, ..., x.

Určite s tým bude potrebovať Vašu pomoc!

Úloha

Matematica začala s \(n\) číslami \(a_i\), indexovanými \(0\) až \(n-1\).

Na zrušenie kliatby budete musieť Kubíkovi pomôcť vykonať \(q\) operácií. Operácie sú troch typov.

Operácia 0 l r v značí ‘pridaj \(v\) všetkým číslam s indexami \(l\) až \(r\)’.

Operácia 1 l r značí ‘vypíš najmenší spoločný násobok čísel \(LCM(a_l), LCM(a_{l+1}), \cdots, LCM(a_r)\)’

Operácia 2 l r značí ‘vypíš najväčší spoločný deliteľ čísel \(LCM(a_l), LCM(a_{l+1}), \cdots, LCM(a_r)\)’

Keďže výsledky operácií 1 a 2 môžu byť obrovské, vypíšte len ich zvyšok po delení \(\ 1\ 000\ 000\ 007\).

Vstup a Výstup

V prvom riadku sú čísla \(n\) a \(q\).

V druhom riadku je začiatočna Matematicina postupnosť \(a_0, a_1, \cdots, a_{n-1}\).

V nasledovných \(q\) riadkoch sú operácie. Pre všetky platí \(0 \leq l \leq r < n\).

Vypíšte odpovede na operácie typu 1 a 2. Keďže môžu byť obrovské, vypíšte len ich zvyšok po delení \(1\ 000\ 000\ 007\).

V prvej sade \(1 \leq n, q, a_i \leq 1\ 000\), a všetky čísla v postupnosti počas všetkých operácií ostanú medzi \(1\) a \(1\ 000\).

V druhej sade \(1 \leq n, q, a_i \leq 300\ 000\), a \(v = 0\).

V tretej sade \(1 \leq n, q, a_i \leq 300\ 000\), a všetky čísla v postupnosti počas všetkých operácií ostanú medzi \(1\) a \(300\ 000\).

Pozor: Optimálne riešenia v jazyku Python nemusia stíhať časový limit v druhej a tretej sade. Takéto riešenia budú po súťaži prehodnotené s vyšším limitom.

Príklad

Input:

5 6
4 2 7 1 5
1 0 2
2 0 2
0 0 3 1
0 2 2 -5
2 3 4
1 0 4

Output:

420
2
2
60

Postupnosť čísel pred poslednou operáciou je \(5 3 3 1 5\). Prepočítané funkciou LCM, ich hodnoty sú \(60, 6, 6, 1, 60\). Ich najmenší spoločný násobok je \(60\).