Sau khi LeVanThuc đột nhập thành công vào ngân hàng, anh ấy tìm thấy ~n~ cái két sắt liên tiếp nhau, két thứ ~i~ chứa số tiền ~a_i~. Anh ta cũng có 1 chiếc chìa khóa có thể kích hoạt một lần. Nếu kích hoạt chìa khóa với mật mã là ~k~ thì số tiền lấy được ở mỗi két sẽ là ~gcd(a_i,k)~. Đụng đến ~gcd~ anh ấy lại bắt đầu ngứa nghề và tự hỏi bản thân rằng, nếu giả sử chìa khóa được kích hoạt mật mã là ~k~ thì tổng số tiền lấy được ở đoạn từ ~l~ đến ~r~ sẽ là bao nhiêu? Bạn hãy cùng anh ấy giải quyết bài toán này nhé.

INPUT

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n, q ( n \leq 10^5, q \leq 10^5)~ .
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_i(a_i \leq 10^7)~ .
• ~q~ dòng tiếp theo mỗi dòng gồm ~3~ số nguyên dương tương ứng là ~l_i~, ~r_i~ và ~k_i~ ~(l_i,r_i \leq n, k \leq 10^4)~.

OUTPUT

• ~q~ dòng gồm ~q~ số nguyên dương là số tiền lấy được với mỗi giả sử của LeVanThuc.

Sample Input

10 5
16 100 51 21 31 32 65 88 1 95 
10 10 10
2 4 4
5 8 6
9 10 5
9 10 3

Sample Output

5
6
6
6
2

Subtask

• ~30~% số test với ~n,q \leq 10^3~
• ~70~% số test còn lại không có ràng buộc thêm