Triple Nested Sum Query

Given a sequence (a_1, a_2, \dots, a_n) of length (n) and (m) queries. For each query, you are given three integers (d), (p_1) and (p_2). Compute the following sum:

[ \sum_{i=0}^{d-1} \sum_{j=0}^{d-1} \sum_{k=0}^{d-1} a_{p_1 + d\cdot i + j}, a_{p_2 + d\cdot j + k} ]

Note: The sequence is 1-indexed and it is guaranteed that all indices accessed are valid.

inputFormat

The first line contains two integers (n) and (m) — the length of the sequence and the number of queries.\nThe second line contains (n) integers (a_1, a_2, \dots, a_n).\nEach of the next (m) lines contains three integers (d, p_1, p_2) describing a single query.

outputFormat

For each query, output a single line containing the computed sum.

sample

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

94