나누고 지배하라 2.0

사슈카는 나눗셈 연산을 매우 좋아한다. 그래서 가을 정보 올림피아드에 나눗셈만 사용하는 문제를 내기로 했다. 문제에는 그가 아끼는 양의 정수 수열 $a_1, a_2, \ldots, a_N$과 $Q$개의 질의가 주어진다. $i$번째 질의는 양의 정수 $l_i$, $r_i$, $d_i$로 표현된다. 각 질의에 대해 수열에서 위치가 $l_i$부터 $r_i$까지인 원소 중 $d_i$의 약수이거나 $d_i$의 배수인 수의 개수를 구한다. 시간이 흐르고 있고 여러분은 1등을 원하므로, 이 질의에 답하는 프로그램 divide.cpp를 작성하라.

첫 줄에 정수 $N$과 $Q$가 주어진다. 둘째 줄에 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 주어진다. 이어지는 $Q$개의 줄에는 각각 $l_i$, $r_i$, $d_i$가 주어진다.

한 줄에 $Q$개의 정수를 출력한다. $i$번째 정수는 $i$번째 질의의 답이다.

$1 ≤ N, Q ≤ 100000$, $1 ≤ a_i, d_i ≤ 200000$, $1 ≤ l_i ≤ r_i ≤ N$. 모든 $1 ≤ i < j ≤ N$에 대해 $a_i e a_j$이다.