소수 클러스터

문제

양의 정수 $x$와 소수 $p$에 대하여, $v_p(x)$를 $x$를 $p$로 연속해서 나눌 수 있는 횟수라고 하자. 즉, $p^k$가 $x$를 나누어떨어지게 하는 음이 아닌 정수 $k$의 최댓값이다.

예를 들어 $72 = 2^3 \cdot 3^2$이므로 $v_2(72)=3$이고 $v_3(72)=2$이다.

길이가 $N$인 양의 정수 수열 $a_1, a_2, \ldots, a_N$과 $Q$개의 쿼리가 주어진다. 각 쿼리에는 구간의 양 끝 $l$, $r$과 소수 $p$가 주어지며, 구간에 있는 수들을 소인수분해 했을 때 $p$가 등장하는 지수의 합을 구해야 한다. 즉, 각 쿼리에 대해 다음 값을 구해 보자.

입력

첫째 줄에 수열의 길이 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 4,000,000; 1 \le Q \le 1,000,000)$

둘째 줄에 $N$개의 양의 정수 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어진다. $(1 \le a_i \le 1,000,000)$

다음 $Q$개의 줄 중 $j$번째 줄에는 $j$번째 쿼리를 나타내는 세 정수 $l_j$, $r_j$, $p_j$가 공백으로 구분되어 주어진다. $(1 \le l_j \le r_j \le N; p_j \le 1,000,000)$

각 $p_j$는 소수이다.

출력

$Q$개의 줄에 각 쿼리의 답을 입력으로 주어진 순서대로 한 줄에 하나씩 출력한다.

예제 1

5 4
12 18 20 7 72
1 5 2
2 5 3
1 3 2
4 5 7

출력 1

8
4
5
1