给定一个包含 $N$ 个整数的数组 $A$（$A_1, \dots, A_N$）和一个整数 $K$。你需要处理 $Q$ 个查询，查询分为以下两种类型：

• 1 i1 i2 ... iK：你需要将 $A_{i_1}, \dots, A_{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：你需要计算序列 $A_l, A_{l+1}, \dots, A_{r-1}, A_r$ 中所有长度为 $m$ 的连续子序列的元素之和。注意，出现在多个子序列中的元素需要被多次累加。

输入格式

输入的第一行包含两个整数 $N$ 和 $K$。第二行包含 $N$ 个整数：数组 $A$ 的元素。第三行包含一个整数 $Q$，表示查询的数量。接下来的 $Q$ 行包含查询，每行描述一个上述类型的查询。

输出格式

输出包含类型 2 查询的答案，每个答案占一行。

数据范围

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

样例

输入 1

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

输出 1

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$。