题目描述

本题译自 eJOI2021 Problem A. Addk

给定一个长为 $N$ 的数组 $A$ 以及整数 $K$。你需要接下来处理 $Q$ 组询问，询问有以下两种：

• $1\,i_1\,i_2\,\dots\,i_K$：你需要将 $A_{i_1},A_{i_2},\dots,A_{i_K}$ 向左循环移位，也就是说 $A_{i_1},A_{i_2},\dots,A_{i_K}$ 的新的值应当是 $A_{i_2},A_{i_3},\dots,A_{i_K}, A_{i_1}$。注意 $i_1,i_2,\dots,i_K$ 是不同的，但不一定递增。
• $2\,l\,r\,m$：你需要将 $A_l,A_{l+1},\dots,A_{r}$ 的所有长为 $m$ 的子区间的和进行求和。注意，出现多次的子区间必须被加多次。

输入格式

第一行输入两个正整数 $N,K$。

接下来一行输入 $N$ 个整数，依次表示 $A_i$。

第三行输入一个正整数 $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$ 类型的，我们必须计算序列 $(2,5,1,9,3,4)$ 中所有长度为 $m=4$ 的子区间的和。这些子区间是 $(2,5,1,9)$，$(5,1,9,3)$，$(1,9,3,4)$。这些元素的和为 $52$。

第二个询问是 $1$ 类型的，我们需要对数组 $A$ 中下标为 $2,5,8$ 的元素进行循环移位。所以 $A$ 数组变为 $(7,9,5,1,6,3,4,2)$。

第三个询问是 $2$ 类型的，我们必须计算序列 $(9,5,1,6,3,4)$ 中所有长度为 $m=3$ 的子区间的和。这些子区间是 $(9,5,1)$，$(5,1,6)$，$(1,6,3)$ 和 $(6,3,4)$。这些元素的和为 $50$。

数据范围与提示

• $0\le A_i\le 10^6$
• $1\le l\le r\le N$
• $1\le m\le r-l+1$