Bạn được cho một dãy số ~a~ gồm ~n~ phần tử và ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên dương ~l,r~. Nhiệm vụ của bạn là với mỗi truy vấn, hãy tính giá trị của:

$$\sum_{i=l}^r a_i\ mod\ (i-l+1)$$

Input

Dòng đầu tiên gồm hai số nguyên dương ~n,q~ tương ứng với số phần tử trong dãy số ~a~ và số truy vấn ~(1\le n,q\le 2\times 10^5)~.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1,a_2,\dots,a_n~ tương ứng với các phần tử trong dãy số ~a\ (1\le a_i\le 2\times 10^5)~.

Cuối cùng là ~q~ dòng, mỗi dòng gồm hai số nguyên dương ~l,r~ mô tả các truy vấn ~(1\le l\le r\le n)~.

Output

In ra ~q~ dòng, mỗi dòng gồm duy nhất một số nguyên không âm là kết quả của truy vấn tương ứng.

Scoring

Subtask ~1~ (~13\%~ số điểm): ~n,q\le 7000~.

Subtask ~2~ (~26\%~ số điểm): ~a_i\le 200~.

Subtask ~3~ (~39\%~ số điểm): ~r=n~.

Subtask ~4~ (~22\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

5 10
6 17 8 14 13
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 1

1
3
5
8
0
2
3
0
1
1