Sum Queries

Jack's brother was playing with an array. Jack saw him tensed and went up to him to find what is the problem. His brother told him that the teacher had given him the assignment to write a program that solves the following problem:

There is an array consisting of \(N\) elements, \(a1, a2, ..., a_n\). There are certain queries asked on the array.

Each query is described by 3 values \(l, r, d\) . For each query, you need to find the sum \(al + a{l + d} + a{l + 2 * d} + ... + a{l + i d}\) such that \(l + i d \le r\).

Help Jack's brother to solve this problem.

INPUT:

The first line of input contains an integer \(N\), denoting the number of elements in the array. \((1 \le N \le 10^4)\).

The next line contains \(N\) space separate integers , \(a1, a2, ..., an\), denoting the array elements. \((0 \le ai \le 10^9)\)

The next line contains \(Q\) denoting the number of queries. \((1 \le Q \le 10^4)\)

Each of the next \(Q\) lines contains three integers \(l, r, d\) denoting the ith query. \((1 \le l \le r \le N, 1 \le D \le 10^5)\)

OUTPUT:

For each query print the required sum.