Cho dãy số nguyên dương gồm \(n\) phần tử \(a_1, a_2, ..., a_n\). Có \(Q\) truy vấn, mỗi truy vấn gồm \(3\) số nguyên dương \((L, R, P)\), yêu cầu với mỗi truy vấn đếm số lượng phần tử chia hết cho số nguyên tố \(P\) trong đoạn \([L ... R]\).

Dữ liệu vào:

• Dòng đầu gồm hai số nguyên dương \(n\) và \(Q\).
• Dòng thứ hai gồm n số nguyên dương \(a_1, a_2, ..., a_n\).
• \(Q\) dòng tiếp theo, mỗi dòng gồm \(3\) số nguyên dương \(L, R\) và \(P\) theo thứ tự \((1 \le L \le R \le n\) và \(P\) là số nguyên tố).

Dữ liệu ra:

• \(Q\) dòng, mỗi dòng là một số nguyên là số số chia hết cho số nguyên tố \(P\) trong đoạn \([L ... R]\).

Input 1

7 2
3 6 9 8 10 14 15
1 7 3
4 7 2

Output 1

4
3

Giới hạn:

• Trong tất cả các test có \(aᵢ \le 10^6\).
• Subtask \(1\): \(n, Q \le 10^4\), \(P \le 10^5\) (3 tests)
• Subtask \(2\): \(n, Q \le 10^5\), \(P \le 10^2\) (3 tests)
• Subtask \(3\): \(n, Q \le 10^5\), \(P \le 10^5\) (4 tests)