Cho dãy gồm \(N\) số nguyên dương đôi một phân biệt \(A = (a_1, a_2, \dots, a_N)\).

Hãy trả lời \(Q\) truy vấn, mỗi truy vấn gồm ba số nguyên dương \(l, r, d\), yêu cầu đếm số phần tử \(a_i\) trong \(A\) thoả mãn:

• \(l \leq i \leq r\)
• \(a_i\) hoặc là ước số của \(d\), hoặc là bội số của \(d\).

Input

• Dòng 1: Hai số nguyên \(N, Q\) — số phần tử của dãy \(A\) và số truy vấn (\(1 \leq N, Q \leq 10^5\)).
• Dòng 2: \(N\) số nguyên dương đôi một phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \leq a_i \leq 2 \cdot 10^5; a_i \neq a_j, \forall i \neq j\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(l, r, d\) (\(1 \leq l \leq r \leq N, 1 \leq d \leq 2 \cdot 10^5\)).

Output

• In ra một dòng gồm \(Q\) số nguyên, số thứ \(i\) là kết quả của truy vấn thứ \(i\).

Example

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

6 1 3 1 2

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N, Q \leq 1000\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc bổ sung.