[THUPC2021 初赛] 区间矩阵乘法

题目描述

给定长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$;共 $m$ 组询问,每次询问给出 $d,p_1,p_2$,求 $$ \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} $$

输入输出格式

输入格式


输入的第一行包含一个数 $n$。 之后一行 $n$ 个数,表示 $a$ 这个序列。 之后一行一个数 $m$。 之后 $m$ 行,每行三个数 $d, p_1, p_2$ 表示一次询问。 $1 \le n, m, a_i \le 2 \times {10}^5$,所有数值为 $[1,{10}^9]$ 以内的整数,询问保证 $a$ 的下标在 $[1,n]$ 内。

输出格式


输出共 $m$ 行,表示每个询问对应的答案,答案对 $2^{32}$ 取模。

输入输出样例

输入样例 #1

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

输出样例 #1

2
22
24
1

说明

**【题目来源】** 来自 2021 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2021)初赛。 题解等资源可在 <https://github.com/THUSAAC/THUPC2021-pre> 查看。