시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB61332147.727%

문제

Сашка много обича операцията деление. Дотолкова я обича, че тя измисли задача, която да даде на Есенния турнир по информатика, свързана само и единствено с нея. Тя включва любимата си редица от $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$.

예제 입력 1

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

예제 출력 1

6 1 3 1 2