题目描述

本题译自 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

数据范围与提示

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