P7140 [THUPC 2021 Preliminary] Interval Matrix Multiplication

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

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 $m$ lines, each being the answer to the corresponding query, taken modulo $2^{32}$.

**[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 . Translated by ChatGPT 5