РАЗДЕЛЯЙ и ВЛАДЕЙ 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$.