Zadanie

Groše v modernej dobe

Počet bodov: 60

Kedy ste naposledy čítali článok o grošoch? To som si aj myslel.

Zato článkom o kryptomenách sa musíte naschvál vyhýbať. Tu sa mu nevyhnete.

Prichádzame totiž s najmodernejšou, najspoľahlivejšou a najvymyslenejšou kryptomenou - Zenitcoin!

Nie sme si ešte vôbec istí ako bude čo fungovať, okrem toho že sa bude musieť ťažiť cez Zenit úlohy.

Aby sme nemuseli byť príliš kreatívni, ťaženie bude založené na podobnom princípe ako s ozajstnými kryptomenami - budeme rozdávať ťažké numerické otázky, a zaujíma nás počet núl na konci výsledku. Aby to nebolo také ľahké, nebudeme sa pýtať na výsledky v desiatkovej sústave, ale v rôznych iných sústavách.

Stačí už len navrhnúť tie otázky. Hm. Dáme vám pole čísel, a každá otázka bude ‘vynásob všetky čísla od \(L\)-tého po \(R\)-té’.

Vstup a výstup

V prvom riadku je číslo \(N\) a \(Q\) - počet čísel v poli a počet otázok.

V druhom riadku je \(N\) čísel \(a_i\), číslovaných od \(1\) po \(N\).

Každý z nasledujúich \(Q\) riadkov je otázka v tvare \(L\ R\ S\) - aký úsek čísel treba vynásobiť, a sústava v ktorej nás zaujíma počet núl na konci výsledku.

Pre každú otázku vypýšte odpoveď do samostatného riadku.

Platí \(1 \leq N,Q \leq 10^5\), \(1 \leq L \leq R \leq N\), \(1 \leq a_i \leq 10^9\) a \(2 \leq S \leq 6\).

Sú štyri sady vstupov.

V prvej navyše platí \(N,Q \leq 500\) a \(S = 2\).

V druhej sade \(N,Q \leq 500\).

Príklad

Input:

5 3
10 8 7 12 9
1 3 2
2 5 5
2 5 6

Output:

4
0
3

\(10*8*7 = 560\), v dvojkovej sústave \(1000110000\). Má na konci štyri nuly. \(8*7*12*9 = 6048\), v päťkovej sústave to je \(143143\), a tento výsledok na konci žiadne nuly nemá.