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

힌트