4. Átriové problémy

Vlejd vystúpil z autobusu. Prišiel práve na internáty a jediné, čo ho ako správneho študenta zaujíma je to, kde zohnať jedlo. Vonku panuje treskúca zima. On však vie, že cestou za jedlom bude musieť ešte prekonať bájny kopec ku átriovým domom¹ a až tam ho čaká odmena, v podobe najlepšej jedálne v Mlynskej doline.

Po chvíli celý uzimený dôjde do jedálne a tam vidí dlhý rad stolov s jedlom. Pri prvom podávajú \(30\) rôznych rezňov, pri druhom \(50\) rôznych šalátov. Inde zas \(10\) druhov koláča a takto by mohla jeho myseľ pokračovať vééľmi dlho. Vidí prichádzať zmrznutých študentov, ktorí už nemyslia na nič iné ako na jedlo. Vtom si uvedomí, ako hlúpo sa hladní študenti správajú.

Každý študent si zoberie tácku a prechádza okolo stolov s jedlom. V jednom momente uvidí na stole, pri ktorom sa práve nachádza, druh jedla, na ktorý má chuť. Zoberie si ho a vtom sa začne správať iracionálne a pažravo. Z každého ďalšieho stolíka si vyberie nejakú vec a prihodí si ju na tácku. Takto pokračuje, pokým si neuvedomí, že už na ďalšie jedlo nemá peniaze. Vtedy skončí s prihadzovaním jedla na tácku, odkráča k pokladni a zaplatí.

Ako to už chodí, každého študenta zaujíma, z koľkých možností má na výber. Vlejd je schopný programátor a tak si povedal, že by skúsil študentom uľahčiť život. Práve prebiehajúce skúškové mu však neumožnuje sústrediť sa na nič iné ako na školu. Pomôžte mu a vyriešte túto úlohu zaňho.

Úloha

V jedálni stojí v jednom dlhom rade \(n\) stolov s jedlom. Na \(i\)-tom stole od začiatku je \(k_{i}\) rôznych druhov jedla. Každé jedlo stojí \(1\) euro.

Ak má teda nejaký študent \(x\) eur a jedlo si začne brať pri \(a\)-tom stole, vydržia mu peniaze až po stolík s číslom \(a+x-1\). Na tácke nakoniec bude mať jednu z \(k_{a} \cdot k_{a+1} \cdot ... \cdot k_{a+x-1}\) možností.

Pre každého študenta vieme, pri ktorom stole si začne brať jedlo a koľko má peňazí. Vypočítajte, z koľkých rôznych možností si môže vybrať.

Tento počet, samozrejme, môže byť veľmi veľké číslo a jednotlivým študentom nemusí dávať priveľký zmysel. Pre každého študenta teda dostanete jeho kapacitu: najväčšie číslo, ktoré si vie predstaviť. Vypíšete zvyšok výsledku po delení týmto číslom.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n, q\) (\(1 \leq n, q \leq 10^{5}\)): počet stolov v jedálni a počet študentov. Na druhom riadku vstupu sa nachádza \(n\) čísel \(k_1, k_2, \dots k_n\) (\(1 \leq k_{i} \leq 100\)), kde číslo \(k_{i}\) udáva počet rôznych možností, z ktorých má študent na výber pri \(i\)-tom stole.

Na každom z ďaľších \(q\) riadkov je popis jedného študenta pozostávajúci z troch čísel \(a, x, m\) (\(1 \leq a \leq n\), \(1 \leq x\) a \(2 \leq m \leq 10^{9}\)). Tie hovoria, že študent si začne brať jedlo pri \(a\)-tom stole (stoly číslujeme od \(1\)), má pri sebe \(x\) peňazí a jeho kapacita je \(m\).

Môžete navyše predpokladať, že každému študentovi dôjdu peniaze najneskôr pri poslednom stole, teda že \(a+x-1 \leq n\).

Formát výstupu

Pre každého študenta vypíšte na samostatný riadok jedno číslo: počet možností, z ktorých má na výber, modulo jeho kapacita.

Hodnotenie

Vaše riešenie bude otestované na \(4\) sadách vstupov. Pre jednotlivé sady platia tieto obmedzenia:

Upozorňujeme, že aj vzorové riešenie napísané v nejakom z pomalších jazykov, napr. v Pythone, nemá prakticky žiadnu šancu proti väčším vstupom.

Príklad

Input:

5 3
20 4 5 7 3
2 2 2
1 4 3
4 2 5

Output:

0
1
1

Prvý súčin vychádza \((4 \cdot 5) \bmod 2 = 0\), druhý \((20 \cdot 4 \cdot 5 \cdot 7) \bmod 3 = 2800 \bmod 3 = 1\) a tretí \(21 \bmod 5 = 1\).