P8165 [eJOI 2021] AddK

You are given an array $A$ containing $N$ integers $A_1,\dots,A_N$ and an integer $K$. You need to perform $Q$ operations of the following two types: - $1$ $i_1$ $i_2$ $\dots$ $i_K$: Replace the values of $A_{i_1},A_{i_2},\dots,A_{i_{K-1}},A_{i_K}$ in order with the values of $A_{i_2},A_{i_3},\dots,A_{i_K},A_{i_1}$. Here $i_1,\dots,i_k$ are pairwise distinct. - $2$ $l$ $r$ $m$: Output the sum of elements over all consecutive subsequences of length $m$ within the interval $[l,r]$.

The first line contains two integers $N,K$. The second line contains $N$ integers, representing the $N$ integers of array $A$. The third line contains one integer $Q$, representing the number of operations. The next $Q$ lines each contain several integers, describing one operation.

Output several lines of integers, which are the results of all type $2$ operations.

#### Sample Explanation For the first query, you need to compute the sum of elements over all consecutive subsequences of length $4$ in $\{2,5,1,9,3,4\}$. These subsequences are $\{2,5,1,9\},\{5,1,9,3\},\{1,9,3,4\}$. Therefore the answer is $52$. For the second query, you need to replace $A_2,A_5,A_8$ in order with the values of $A_5,A_8,A_2$. After the replacement, the array becomes $\{7,9,5,1,6,3,4,2\}$. For the third query, you need to compute the sum of elements over all consecutive subsequences of length $3$ in $\{9,5,1,6,3,4\}$. These subsequences are $\{9,5,1\},\{5,1,6\},\{1,6,3\},\{6,3,4\}$. Therefore the answer is $50$. #### Constraints **This problem uses bundled testdata.** - Subtask 1 (36 pts): $1 \le N,Q \le 10^4$ and $K=1$. - Subtask 2 (56 pts): $10001 \le N,Q \le 10^5$ and $K=1$. - Subtask 3 (8 pts): $1 \le N,Q \le 10^5$ and $2 \le K \le 10$. For $100\%$ of the testdata, $0 \le A_i \le 10^6$, $1 \le l \le r \le N$, $1 \le m \le r-l+1$. #### Notes This problem is translated from [eJOI2021](https://sepi.ro/ejoi/2021) Day 1 A AddK. Translated by ChatGPT 5