5. Insektológia v Slovakistane

Tuhá zima už odišla, a tak majú farmári Slovakistanu plné ruky práce vysádzaním plodín na svojich poliach. Na veľké potešenie škodcov všetkého možného druhu, ktorí majú zas plné ústa práce ich vyjedaním.

Insektológ Kubík bol však odhodlaný svojim spoluobčanom pomôcť, a tak cez celé zimné prázdniny pracoval na revolučnom spôsobe, akým by sa škodci a polia dali vyjadriť číslami. Vďaka tomu by určite vedel poradiť farmárom, ako najlepšie ochrániť úrodu pred škodcami.

Svoj návrh predviedol pred KSP¹, avšak neuspel – jeho abstraktné teórie boli síce fascinujúce, no keď prišlo na predvádzanie v praxi, ani so svojimi vytrénovanými kalkulačkovými schopnosťami nevedel dostatočne rýchlo odpovedať, ako najlepšie by sa dala ochrániť Slovakistanská úroda.

Kubík sa však nevzdal a poslal holuba do ďalekej krajiny, v ktorej vraj nažívajú šikovní programátori, ktorí by mu boli schopní pomôcť…

Úloha

Kubík každému škodcovi priradil prvočíslo – čím viac škody narobí, tým väčšie. Každému poľu potom vie priradiť číslo reprezentujúce škodcov, ktorí sa na ňom priživujú – prvočíslo každého prítomného škodcu umocní na mocninu zodpovedajúcu závažnosti zamorenia týmto škodcom a tieto mocniny potom vynásobí dokopy. Výsledné číslo budeme volať kontaminácia poľa. Prvočíselný rozklad kontaminácie poľa nám teda hovorí, ktoré druhy na poli škodia a mocniny jednotlivých prvočísel v rozklade poukazujú na závažnosť zamorenia. Navyše, kontaminácia poľa vyjadruje celkovú škodu, ktorú škodce na danom poli napáchajú.

Polia v Slovakistane sú všetky popri veľtoku Dujana. KSP vlastní lietadlo, ktorým vie postriekať súvislý úsek polí nejakým pesticídom, ktorý je špecificky určený na boj proti jednému druhu škodcov. Každý rok si lámu hlavu nad tým, ktoré pesticídy by mali kam nastriekať, aby zachránili čo najviac úrody.

Kubíkova teória na to však má odpoveď – keď postriekame pole pesticídom proti škodcovi s priradeným prvočíslom \(p\), kontamináciu tohto poľa vydelíme mocninou \(p\), ktorá je v jej rozklade. Rozdiel medzi originálnou a novou kontamináciou je potom množstvo úrody, ktoré sme vďaka pesticídu zachránili.

KSP má veľa návrhov, ktorý pesticíd kam nastriekať. Pre každý z nich povedzte, koľko úrody by tento zákrok zachránil.

Formát vstupu

V prvom riadku sú tri čísla \(n\), \(q\) a \(p\) – počet polí v Slovakistane, počet návrhov kam nastriekať pesticíd, a najväčšia možná kontaminácia poľa.

V druhom riadku vstupu je \(n\) kladných celých čísel \(v_1, v_2, \dots, v_n\) (\(1 \leq v_i \leq p\)) – hodnoty kontaminácie jendotlivých polí, v poradí v akom sú popri veľtoku Dujana.

Nakoniec nasleduje \(q\) riadkov s tromi číslami \(l_i, r_i, p_i\). Tieto tri čísla popisujú návrh KSP, aby sa všetky polia od \(l_i\)-tého až po \(r_i\)-té (vrátane) postriekali pesticídom proti škodcovi s číslom \(p_i\). Platí \(1 \leq l_i \leq r_i \leq n\) a \(1 \leq p_i \leq p\). Číslo \(p_i\) je vždy prvočíslo.

Formát výstupu

Pre každý návrh povedzte, koľko úrody by bolo zachránenej, ak by sa vykonal. Formálne, povedzte o koľko by sa zmenil súčet čísel \(v_{l_i} + \dots + v_{r_i}\), ak by sme každé vydelili tou mocninou prvočísla \(p_i\), ktorá sa v ňom nachádza.

Hodnotenie

Pre jednotlivé testovacie sady platia nasledovné obmedzenia:

Upozorňujeme, že riešenia v pomalých jazykoch, ako Python, nemusia stíhať.

Príklady

Input:

5 5 100
10 20 30 40 50
1 1 2
1 5 5
1 5 47
2 4 3
2 4 2

Output:

5
128
0
20
65

V štvrtom návrhu dostávame rozdiel súčtu \((20+30+40)-(20+10+40) = 20\).