Given a sequence $a_1, a_2, \dots, a_n$ of length $n$, there are $m$ queries. Each query provides $d, p_1, p_2$, and you are asked to calculate:

$$\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}$$

Input

The input is read from standard input. The first line contains an integer $n$. The next line contains $n$ integers, representing the sequence $a$. The next line contains an integer $m$. The next $m$ lines each contain three integers $d, p_1, p_2$, representing a query.

$1 \le n, m, a_i \le 2 \times 10^5$. All values are integers within $[1, 10^9]$. It is guaranteed that the indices of $a$ in the queries are within $[1, n]$.

Output

Output to standard output. Output $m$ lines, each representing the answer to the corresponding query, modulo $2^{32}$.

Examples

Input 1

5
2 2 1 2 1
4
1 5 4
2 2 1
2 1 1
1 5 5

Output 1

2
22
24
1