Zadanie

Jaro, Janka, Jozef, Ja…

Počet bodov: 75

Ja mám veľa kamarátov. Chcem im kúpiť gumené koníky. Tak som zašiel na internetovú webstránku gumene.koniky.xyz - najpopulárnejší obchod s gumennými koníkmi! A veru, v sekcií gumené koníky (jediná sekcia v obchode) som našiel na výber z \(N\) balíkov plných gumených koníkov. Ten e-shop ešte nemajú úplne premyslený - viem si zvoliť súvislý úsek balíkov a kúpiť si ich. To je však problém - ja mám totiž každý deň iný počet kamarátov \(k_i\) (dakedy viac, dakedy menej), a teda v daný deň mám záujem len o balíky v ktorých je počet gumených koníkov deliteľný \(k_i\) - každý balík gumených koníkov má unikátknu chuť, a potrebujem z neho koníkov rozdeliť rovnomerne. Trhanie koníkov je, samozrejme, zakázané.

Keďže chcem s kamarátmi jesť gumené koníky, a nie rátať dáke deliteľnosti čísel na intervaloch, tento problem spadá na vás.

Úloha

V eshope na gumene.koniky.xyz je za radom \(N\) balíkov gumených koníkov. \(Q\) dní si chcem kúpiť nejaký súvislý úsek z nich, pričom v deň \(i\) mám \(k_i\) kamarátov.

Pre každý takýto úsek potrebujem vedieť, koľko balíkov v ňom viem rovnomerne rozdeliť medzi svojich kamarátov - teda počet koníkov v ňom je deliteľný \(k_i\).

Vstup

V prvom riadku vstupu je číslo \(1 \leq N\) - počet balíkov v eshope.

V druhom riadku vstupu sú kladné čísla \(b_1, b_2, \cdots, b_N\) - počet koníkov v balíkoch.

V treťom riadku vstupu je číslo \(1 \leq Q\) - počet otázok.

Každý z ďalších \(Q\) riadkov obsahuje tri čísla \(l_i\ r_i\ k_i\) - ľavý a pravý koniec úseku, ktorý si chcem z eshopu kúpiť, a počet mojich kamarátov v daný deň. Platí \(1 \leq l_i \leq r_i \leq N\), a \(1 \leq k_i\).

V sadách platia nasledovné obmedzenia:

\(N \leq 10^5\)

\(b_i, k_i \leq 10^1, 10^4, 10^5\)

\(Q \leq 10^5, 2 \cdot 10^4, 10^5\)

Výstup

Pre otázku číslo \(i\) vypíšte jedno číslo - počet balíkov od \(l_i\)-teho po \(r_i\)-tý, v ktorých je počet koníkov deliteľný \(k_i\).

Príklady

Input:

5
5 4 3 2 1
2
1 5 1
1 5 2

Output:

5
2

Všetky čísla sú deliteľné jednotkou. Len dve sú párne.

Input:

5
9 12 5 32 12
3
1 5 2
1 3 3
2 4 2

Output:

3
2
2