JumpSum

Cerință

Se dă un șir $a_1, a_2, \dots, a_n$.

Primiți $q$ întrebări de tipul $x, y$. Pentru fiecare întrebare voi va trebui să afișați $\sum_{i=x,i-=y}^{i \ge 1} a_i$. Mai exact, afișați $a_x + a_{x-y} + a_{x-2y} + \dots + a_{x-ky}$ cu $k$ maxim astfel încât $x-ky>=1$ pentru fiecare întrebare.

Date de intrare

Se va citi $n$ urmat, pe a doua linie, de cele $n$ valori ale șirului. Pe a treia linie se află $q$ iar pe următoarele $q$ linii se vor afla câte 2 numere $x$ și $y$ cu semnificația din enunț.

Date de ieșire

Se vor afișa $q$ linii. Pe a $i$-a linie se va afla răspunsul pentru întrebarea $i$, în ordinea citirii.

Restricții și precizări

• $1 \le n, q \le 10^5$;
• $1 \le x, y \le n$, pentru fiecare $q$;
• $-10^9 \le a_i \le 10^9$;
• Pentru $20$ de puncte, $1 \le n, q \le 10^3$;
• Pentru alte $20$ de puncte, $1 \le y \le 10$, pentru fiecare $q$.

Exemplu

stdin

8
3 2 -1 4 8 1 6 6
4
3 2
8 3
4 3
6 1

stdout

2
16
7
17

Explicatie

Pentru prima interogare se cere $a_3 + a_1$.
Pentru a doua interogare se cere $a_8 + a_5 + a_2$.
Pentru a treia interogare se cere $a_4 + a_1$.
Pentru a patra interogare se cere $a_6 + a_5 + a_4 + a_3 + a_2 + a_1$.