Problem 3182: mogger

Cerință

Pentru un vector $A$ cu $N$ numere se definește costul unui interval în felul următor:

int f(int l, int r){
	int cost = 0;
	for(int i = l; i <= r; i += A[i])
    	cost += A[i];
	return cost;
}

Se dă un vector $P$ cu $N$ elemente și un număr $Q$ , iar voi trebuie să răspundeți la $Q$ întrebări de forma: pentru $l$ și $r$ date ( $l \leq r$ ) calculați $\displaystyle \sum_{i=l}^{r} f(i,r)$ .

Date de intrare

Pe prima linie se află $N$ și $Q$ , numărul de elemente din vector respectiv numărul de întrebări. Pe următoarea linie se află $N$ numere naturale separate prin câte un spațiu. Pe următoarele $Q$ linii se află exact $2$ numere ( $l$ și $r$ ).

Date de ieșire

Pe fiecare dintre cele $Q$ linii se va afla răspunsul la întrebarea respectivă.

Restricții și precizări

$1 \leq N,Q \leq 2 \cdot 10^5$
$1 \leq A_i \leq 30$

Exemplul 1

stdin

10 6
6 2 3 3 3 6 4 6 3 2 
3 9
1 7
3 7
3 9
5 10
2 6

stdout

Exemplul 2