B. Yet another vector problem
time limit per test
0.25 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

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.

Input

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)

Output

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

Examples
Input
3 3
1 2 3
0 1
0 2
1 2
Output
6
4
2