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)~.

Yêu cầu: 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 \le i \le 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 \le N, Q \le 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 \le a_i \le 2 \cdot 10^5; a_i \ne a_j \forall i \ne j)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~l, r, d~ ~(1 \le l \le r \le N, 1 \le d \le 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~.

Scoring

Sample Input 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

Sample Output 1

6 1 3 1 2

Notes

Truy vấn 1: ~Q([12, 10, 3, 18, 6, 72, 28, 42], 6) \Rightarrow \{12, 3, 18, 6, 72, 42\}~ (có 6 phần tử).

Truy vấn 2: ~Q([3, 18, 6, 72, 28], 7) \Rightarrow \{28\}~ (có 1 phần tử).

Truy vấn 3: ~Q([10, 3, 18, 6, 72], 9) \Rightarrow \{3, 18, 72\}~ (có 3 phần tử).

Truy vấn 4: ~Q([12, 10, 3, 18, 6], 5) \Rightarrow \{10\}~ (có 1 phần tử).

Truy vấn 5: ~Q([18, 6, 72, 28, 42], 4) \Rightarrow \{72, 28\}~ (có 2 phần tử).