Ước chung trên đoạn con

Trong buổi huấn luyện hôm nay, các bạn sẽ được thử thách với một bài toán cổ điển nhưng đòi hỏi tư duy phân tích sâu sắc. Giả sử chúng ta có một dãy số nguyên dương \(a\) gồm \(n\) phần tử, được đánh số từ \(1\) đến \(n\). Dãy số này tượng trưng cho các "mốc" năng lượng trên một đường đua thuật toán.

Để đánh giá khả năng xử lý truy vấn và tối ưu hóa, giảng viên đưa ra \(q\) truy vấn. Mỗi truy vấn có dạng \((l, r, d)\), yêu cầu các bạn đếm xem có bao nhiêu đoạn con nằm hoàn toàn trong đoạn từ \(l\) đến \(r\) có ước chung lớn nhất (GCD) không vượt quá \(d\).

Nói cách khác, với mỗi truy vấn, các bạn cần tìm số cặp chỉ số \((u, v)\) sao cho:

• \(l \le u \le v \le r\).
• \(\text{gcd}(a_u, a_{u+1}, \dots, a_v) \le d\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 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 \le 100\).
• \(30\%\) số test có \(n, q \le 1000\).
• \(30\%\) số test có \(d\) là hằng số, \(n, q \le 100000\).
• \(20\%\) số test còn lại không có ràng buộc gì thêm.