Description

You are given a sequence $a_1, a_2, \dots, a_n$ of length $n$. There are $m$ queries. Each query gives $d, p_1, p_2$. Compute

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

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$, describing one query.

Constraints: $1 \le n, m, a_i \le 2 \times {10}^5$. All values are integers within $[1,{10}^9]$. The queries guarantee that the indices of $a$ are within $[1,n]$.

Output Format

Output $m$ lines, each being the answer to the corresponding query, taken modulo $2^{32}$.

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

2
22
24
1

Hint

[Source]

From the THUPC2021 Preliminary Round of the 2021 Tsinghua University Student Algorithm Competition and University Invitational Contest (THUPC2021).

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2021-pre.

Translated by ChatGPT 5