题目描述

给定一个包含 $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$ 的结果。

8 3
7 2 5 1 9 3 4 6
3
2 2 7 4
1 2 5 8
2 2 7 3

52
50

提示

样例解释

第一次询问需要求出 $\{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 Day 1 A AddK。