402368: GYM100739 B Yet another vector problem

You're given a 0-based array a of length n. Answer Q queries of form: what is sum of elements a[i], such as i modulo p = q, for given p and q.

The first line of the input contains numbers n and Q (1 ≤ n, Q ≤ 100000). Next n lines contain the array a. Each element of a is between 1 and 100. Next Q lines describe the queries by two integers p and q (0 ≤ q ≤ p ≤ n - 1)

The output contains Q lines, corresponding to answers of the queries.

3 3
1 2 3
0 1
0 2
1 2

6
4
2