Problem Description

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]$.

Input Format

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 Format

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

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

Hint

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 Day 1 A AddK.

Translated by ChatGPT 5