给定长度为 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} 取模。