题目描述

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

1. 1 i₁ i₂ … iₖ：你需要将 $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. 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$