Bạn Minh được cho trước một dãy số nguyên dương gồm ~N~ phần tử ~a_1, a_2, \ldots, a_N~. Bạn cần thực hiện ~Q~ truy vấn, trong đó mỗi truy vấn ứng với một đoạn con ~[L, R]~ của dãy trên với ~1 \leq L \leq R \leq N~ và cần tính tổng của tất cả các giá trị ~a_i \% a_j~ (~a_i~ chia lấy phần dư cho ~a_j~) với mọi cặp chỉ số ~(i, j)~ thỏa mãn ~L \leq i, j \leq R~.

Yêu cầu: Hãy viết chương trình giúp Minh trả lời các truy vấn đó.

Input

Dữ liệu vào từ file THAOTAC.INP:

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ cho biết số phần tử trong dãy và số lượng truy vấn.

• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~.

• Trong ~Q~ dòng tiếp theo, mỗi dòng là một cặp số nguyên ~L, R~ (~1 \leq L \leq R \leq N~).

Output

Ghi ra file THAOTAC.OUT gồm ~Q~ số trên các dòng khác nhau, mỗi dòng là câu trả lời các truy vấn đã cho theo thứ tự.

Scoring

Sample Input 1

3 2
1 2 4
1 3
2 2

Sample Output 1

4
0