Zadanie

Krkolomná Chémia

Počet bodov: 90

MacGyver sa opäť ocitol v zapeklitej situácií! Neprajníci ho nechali na pospas v opustenej bani. Svetla nieje dosť, vzduchu ešte menej, a z tejto šlamastiky sa bude musieť dostať len za pomocou troch spiniek, vybitého mobilu, nedojedenej horalky, pár kusov ovocia, a nespočetného množstva chemického odpadu, ktorý vláda do bane nasúkala v sedemdesiatych rokoch.

Zo spiniek a ovocia rýchlo zhotovil funkčný zdroj elektriny. Z funkčného zdroju elektriny a vybitého mobilu zostrojil nabitý mobil. Okamžite vám aj zavolal, lebo nepozná lepšieho čarodeja chemikálií ako Vás - a popri dojedaní horalky vám aj vysvetlil, aká je jediná nádej na únik z tejto šlamastiky…

Úloha

Chémia v MacGyverovom svete funguje jednoducho - každá základná prísada má pridelené prvočíslo. Každá komplexná chemikália sa potom dá reprezentovať celým číslom - jeho rozklad na prvočísla určí jej jednotlivé prísady, pričom vyššie mocniny značia vyššie potencie.

Aby MacGyver zostrojil únikovú bombu, bude musieť namiešať fakt špeci chemikáliu. Keď MacGyver zmieša chemikálie s číslami \(x\) a \(y\), vytvorí vďaka MacGyverovským pravidlám chémie látku s číslom, ktorá je najmenším spoločným násobkom \(x\) a \(y\) (odteraz NSN).

V bani má k dispozícií rad \(n\) nádob s chemickým odpadom - číslami od \(1\) po \(10^5\).

Bude sa vás postupne pýtať otázky ‘ak zmiešam chemikálie v nádobách od \(L\)-tej po \(R\)-tú, akú látku namiešam?’.

Zároveň však musí uvažovať s možnosťou, že dlhoročné skladovanie chemikálií v bani mohlo vynulovať potenciu nejakej základnej prísady. Bude vás teda tiež informovať vetou ‘dokým nepoviem inak, uvažujme, že prísada \(x\) v našich chemikáliách stratila všetku potenciu’.

Stíhate MacGyverovi poradiť?

Vstup a Výstup

V prvom riadku vstupu sú čísla \(n\) a \(q\) - počet nádob s chemikáliami a počet MacGyverovich dotazov.

V druhom riadku je \(n\) celých čísel v rozsahu \(1\) až \(10^5\) - čísla chemikálií v nádobách \(1\) až \(n\).

V každom z nasledovných \(q\) riadkov je jeden MacGyverov príkaz. Ten je buď

\(0 L R\), označujúc otázku ‘aký je NSN chemikálií v nádobách od \(L\)-tej po \(R\)-tú?’. \(1 \leq L \leq R \leq n\).

alebo

\(1 x\), značiac ‘kým nepríde ďalší takýto príkaz, neber prvočíslo \(x\) do úvahy’. \(1 \leq x \leq 10^5\), a \(x\) je buď prvočíslo, alebo špeciálne hodnota \(1\), ktorá značí, že sa nemá žiadne prvočíslo pri výpočtoch NSN ignorovať.

Na každý príkaz typu \(0 L R\) vypíšte vypočítaný NSN. Keďže môže byť fakt veľký, vypíšte len jeho zvyšok po delení \(10^9+7\).

Na tretinu bodov stačí vyriešiť vstupy s \(1 \leq n,q \leq 1\,000\).

Na druhú tretinu bodov stačí vyriešiť vstupy s \(1 \leq n,q \leq 50\,000\), a nebudú sa vyskytovať žiadne príkazy typu \(1 x\).

Na finálnu tretinu bodov potrebujete vyriešiť vstupy s \(1 \leq n \leq 50\,000\) a \(1 \leq q \leq 10^5\).

Príklad

Input:

7 9
4 2 3 15 98765 47477 1
0 1 4
1 3
0 1 4
1 2
0 1 4
0 1 2
1 1
0 1 7
0 7 7

Output:

60
20
15
1
268790468
1

NSN prvých štyroch čísel je 60. Ak však poignorujeme trojky, je to 20, a ak dvojky, tak zasa 15. V piatom prípade 56268790860 mod 1000000007 = 268790468.