Cho dãy gồm ~N~ số nguyên dương đôi một phân biệt ~a_1, a_2, \dots, 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 vị trí ~r_i~ trong dãy là ước số hoặc bội số của ~d_i~. 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~ (~N \ge 1~, ~Q \le 10^5~).
• Dòng 2: gồm ~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~, ~1 \le i \le 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 \le l_i \le r_i \le N~; ~1 \le d_i \le 2 \cdot 10^5~; ~1 \le i \le Q~).

Kết quả

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

Ví dụ

squery.inp

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

squery.out

6 1 3 1 2

Giải thích: Trong truy vấn 1: các số trong đoạn từ vị trí 1 đến 8 là ước hoặc bội của 6 gồm: 12, 3, 18, 6, 72, 42.

Giới hạn

• Subtask 1 (80% số điểm): ~Q = 1~.
• Subtask 2 (10% số điểm): ~N, Q < 10000~.
• Subtask 3 (10% số điểm): không có ràng buộc bổ sung.