РАЗДЕЛЯЙ и ВЛАДЕЙ 2.0

Сашка много обича операцията деление. Дотолкова я обича, че тя измисли задача, която да даде на Есенния турнир по информатика, свързана само и единствено с нея. Тя включва любимата си редица от $N$ цели, положителни числа $a\_1$, $a\_2$, $\dots$, $a\_N$ и $Q$ въпроса, съответно $i$-тият от тях характеризиран от три цели положителни числа $l\_i$, $r\_i$ и $d\_i$. Въпросите са за броя числа на позициите от $l\_i$ до $r\_i$ в редицата, които са делители или са кратни на $d\_i$. Тъй като времето тече, а Вие копнеете за първото място, Вие се захващате да напишете програма divide.cpp, която да отговори на въпросите.

На първия ред от стандартния вход са дадени целите, положителни числа $N$ и $Q$, съответно броят числа в редицата и броят въпроси. На втория ред от стандартния вход са дадени $N$ числа $a\_1$, $a\_2$, $\dots$, $a\_N$. На останалите $Q$ реда от стандартния вход са описани въпросите, като съответно на $i$-тият ред са дадени трите числа, които характеризират $i$-тия въпрос, а именно $l\_i$, $r\_i$ и $d\_i$.

На стандартния изход изведете един ред, съдържащ $Q$ числа, като $i$-тото от тях да е равно на отговора на $i$-тият въпрос.

• $1 ≤ N,Q ≤ 100\\, 000$
• $1 ≤ a\_i, d\_i ≤ 200\\, 000$
• $1 ≤ l\_i ≤ r\_i ≤ N$
• $a\_i \ne a\_j$ за всички $1 ≤ i < j ≤ N$.