AddK

You are given an array $A$ of $N$ integers $A_1, \dots, A_N$ and an integer $K$. You must process $Q$ queries of the following two types:

• $1 \, i_1 \, i_2 \, \dots \, i_K$: circularly permute $A_{i_1}, \dots, A_{i_K}$ to the left. That is, the new values of $A_{i_1}, A_{i_2}, \dots, A_{i_{K-1}}, A_{i_K}$ are $A_{i_2}, A_{i_3}, \dots, A_{i_K}, A_{i_1}$. The indices $i_1, \dots, i_K$ are distinct and not necessarily in increasing order.
• $2 \, l \, r \, m$: sum the elements of all contiguous subsequences of length $m$ from the sequence $A_l, A_{l+1}, \dots, A_{r-1}, A_r$. An element that appears in multiple subsequences is added once for each subsequence it appears in.

The first line contains two integers, $N$ and $K$. The second line contains $N$ integers: the elements of array $A$. The third line contains an integer $Q$, the number of queries, and the next $Q$ lines contain the queries, each of one of the two types described above.

Output the answer to each type 2 query, one per line.

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

The first query is of type 2, and we must sum the elements of all contiguous subsequences of length $m = 4$ from the sequence $(2, 5, 1, 9, 3, 4)$. Those subsequences are $(2, 5, 1, 9)$, $(5, 1, 9, 3)$, $(1, 9, 3, 4)$, and the sum of their elements is 52.

The second query is of type 1, and it circularly permutes the elements of array $A$ at indices $2$, $5$, $8$. Array $A$ becomes $(7, 9, 5, 1, 6, 3, 4, 2)$.

The third query is of type 2, and we must sum the elements of all contiguous subsequences of length $m = 3$ from the sequence $(9, 5, 1, 6, 3, 4)$. Those subsequences are $(9, 5, 1)$, $(5, 1, 6)$, $(1, 6, 3)$, $(6, 3, 4)$, and the sum of their elements is $50$.