Cho dãy gồm \(N\) số nguyên dương đôi một phân biệt \(a_1,a_2,…,a_N\). Tèo cần trả lời \(Q\) truy vấn, truy vấn thứ \(i\) cho ba số nguyên dương \(l_i,r_i,d_i\) với yêu cầu xác định xem có bao nhiêu số từ vị trí \(l_i\) đến \(r_i\) trong dãy là ước số hoặc bội số của \(d_i\).

Yêu cầu: Bạn hãy lập trình giúp Tèo trả lời các truy vấn nhé!

Dữ liệu:

• Dòng 1: Gồm hai số nguyên \(N,Q (1≤N,Q≤10^5)\);

• Dòng 2: Gồm \(N\) số nguyên dương đôi một phân biệt \(a_1,a_2,…,a_N (1≤a_i≤2⋅10^5, 1≤i≤N); \)

• Tiếp theo là \(Q\) dòng, mỗi dòng mô tả một truy vấn gồm ba số nguyên \(l_i,r_i,d_i (1≤l_i≤r_i≤N; 1≤d_i≤2⋅10^5,1≤i≤Q).\)

Kết quả:

• Ghi trên một dòng duy nhất gồm \(Q\) số nguyên, số thứ \(i (1≤i≤Q)\) là câu trả lời cho truy vấn thứ \(i\).

Ràng buộc:

• Subtask 1: 80% số điểm có \(Q=1\);

• Subtask 2: 10% số điểm có \(N,Q≤1000;\)

• Subtask 3: 10% số điểm không có ràng buộc bổ sung.

Sample Input

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

6 1 3 1 2