Truy vấn GCD

Cho một dãy \(a\) gồm \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3}, ..., a_{n}\) \((a_{i} \leq 10^9)\).

Yêu cầu:
Có \(q\) truy vấn có dạng \(l, r, d\). Với mỗi truy vấn, bạn cần đếm xem có bao nhiêu đoạn con nằm trong đoạn từ \(l\) đến \(r\) có ước chung lớn nhất không vượt quá \(d\). Nói một cách cụ thể hơn, hãy đếm xem có bao nhiêu cặp \((u, v)\) sao cho:

• \(l \leq u \leq v \leq r\).
• \(gcd(a_{u}, a_{u + 1}, a_{u + 2}, ..., a_{v}) \leq d\).

Input

• Dòng đầu tiên là \(2\) số \(n\) và \(q\) \((1 \leq n, q \leq 2.10^5)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_{1}, a_{2}, a_{3}, ..., a_{n}\) \((a_{i} \leq 10^9)\).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số \(l, r, d\).

Output

• Với mỗi truy vấn, in kết quả ra trên một dòng.

Example

6 5
3 9 6 2 8 4
1 5 3
2 4 3
1 5 4
2 6 2
1 6 1

12
4
12
9
6

Scoring

• \(20\%\) số test có \(n, q \leq 100\).
• \(30\%\) số test có \(n, q \leq 1000\).
• \(30\%\) số test có \(d\) là hằng số, \(n, q \leq 100000\) (với mọi truy vấn, \(d\) luôn không thay đổi).
• \(20\%\) số test còn lại không có ràng buộc gì thêm.