P8165 [eJOI 2021] AddK

给定一个包含 $N$ 个整数 $A_1,\dots,A_N$ 的数组 $A$ 和一个整数 $K$。你需要进行 $Q$ 次操作，包括下列两种类型： - $1$ $i_1$ $i_2$ $\dots$ $i_K$：将 $A_{i_1},A_{i_2},\dots,A_{i_{K-1}},A_{i_K}$ 的值依次替换为 $A_{i_2},A_{i_3},\dots,A_{i_K},A_{i_1}$ 的值。其中，$i_1,\dots,i_k$ 互不相同。 - $2$ $l$ $r$ $m$：输出 $[l,r]$ 区间内所有长度为 $m$ 的连续子序列的元素和。

第一行两个整数 $N,K$。 第二行 $N$ 个整数，表示数组 $A$ 的 $N$ 个整数。 第三行一个整数 $Q$，表示操作次数。 接下来 $Q$ 行，每行若干个整数，表示一次操作。

输出包含若干行整数，即为所有操作 $2$ 的结果。

#### 样例解释 第一次询问需要求出 $\{2,5,1,9,3,4\}$ 中所有长度为 $4$ 的连续子序列的元素和。这些子序列包括 $\{2,5,1,9\},\{5,1,9,3\},\{1,9,3,4\}$。因此答案为 $52$。 第二次询问需要将 $A_2,A_5,A_8$ 依次替换为 $A_5,A_8,A_2$ 的值。替换后数组变为 $\{7,9,5,1,6,3,4,2\}$。 第三次询问需要求出 $\{9,5,1,6,3,4\}$ 中所有长度为 $3$ 的连续子序列的元素和。这些子序列包括 $\{9,5,1\},\{5,1,6\},\{1,6,3\},\{6,3,4\}$。因此答案为 $50$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（36 pts）：$1 \le N,Q \le 10^4$ 且 $K=1$。 - Subtask 2（56 pts）：$10001 \le N,Q \le 10^5$ 且 $K=1$。 - Subtask 3（8 pts）：$1 \le N,Q \le 10^5$ 且 $2 \le K \le 10$。 对于 $100\%$ 的数据，$0 \le A_i \le 10^6$，$1 \le l \le r \le N$，$1 \le m \le r-l+1$。 #### 说明 本题译自 [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 A AddK。