Setsuna, a lovely girl who likes to play with data structures, is going to share an interesting problem with you which is called $K$-Shift.
An array $A$ can be $K$-Shifted if and only if the length of array $A$ can be divided by $K$ (i.e., $| A |$ must be a multiple of $K$).
When Setsuna $K$-Shift the array $A$, the following events will happen in order:
For example, we have $A = {1, 2, 3, 4, 5, 6}$ now. If Setsuna $3$-Shift it , it will become ${2, 3, 1, 5, 6, 4}$.
Now, you have an array $A$ of length $n$ ($1$-indexed). Setsuna will perform two kinds of operations on it:
The first line contains two integers $n$ and $m$ ($3 <= n, m <= 2 times 10^5$), which indicates the length of the array $A$, and the number of the operations Setsuna will perform.
The second line contains $n$ integers $a_1, a_2, \\\\cdots, a_n (1 <= a_i <= 10^9)$.
The $i$-th of the next $m$ lines contains four integers $1, l_i, r_i, K_i (1 <= l_i < r_i <= n, 2 <= K_i <= 3, K_i | (r_i -l_i + 1))$ or three integers $2, l_i, r_i (1 <= l_i <= r_i <= n)$, which respectively represent two different operations.
Output the answer to the corresponding operation $2$ in each line.
After the first operation, ${1, 2, 3, 4, 5, 6}$ will become ${2, 1, 4, 3, 5, 6}$.
The sum of elements of indexes in $[ 2, 3 ]$ is $1 + 4 = 5$.
After the third operation, ${2, 1, 4, 3, 5, 6}$ will become ${1, 4, 2, 5, 6, 3}$.
The sum of elements of indexes in $[ 2, 6 ]$ is $4 + 2 + 5 + 6 + 3 = 20$.
## Input
The first line contains two integers $n$ and $m$ ($3 <= n, m <= 2 times 10^5$), which indicates the length of the array $A$, and the number of the operations Setsuna will perform.The second line contains $n$ integers $a_1, a_2, \\\\cdots, a_n (1 <= a_i <= 10^9)$.The $i$-th of the next $m$ lines contains four integers $1, l_i, r_i, K_i (1 <= l_i < r_i <= n, 2 <= K_i <= 3, K_i | (r_i -l_i + 1))$ or three integers $2, l_i, r_i (1 <= l_i <= r_i <= n)$, which respectively represent two different operations.
## Output
Output the answer to the corresponding operation $2$ in each line.
[samples]
## Note
After the first operation, ${1, 2, 3, 4, 5, 6}$ will become ${2, 1, 4, 3, 5, 6}$.The sum of elements of indexes in $[ 2, 3 ]$ is $1 + 4 = 5$.After the third operation, ${2, 1, 4, 3, 5, 6}$ will become ${1, 4, 2, 5, 6, 3}$.The sum of elements of indexes in $[ 2, 6 ]$ is $4 + 2 + 5 + 6 + 3 = 20$.
**Definitions**
Let $ A = (a_1, a_2, \dots, a_n) $ be a 1-indexed array of integers.
Let $ m $ be the number of operations.
**Operations**
Two types of operations are defined:
1. **Type 1 (K-Shift on subarray)**: Given $ l_i, r_i, K_i $ with $ K_i \in \{2,3\} $ and $ K_i \mid (r_i - l_i + 1) $:
Let $ L = r_i - l_i + 1 $, and partition the subarray $ A[l_i:r_i] $ into $ \frac{L}{K_i} $ contiguous blocks of size $ K_i $.
For each block $ B_j = (a_{l_i + (j-1)K_i}, a_{l_i + (j-1)K_i + 1}, \dots, a_{l_i + jK_i - 1}) $, perform a left rotation:
$$
B_j \mapsto (a_{l_i + (j-1)K_i + 1}, a_{l_i + (j-1)K_i + 2}, \dots, a_{l_i + jK_i - 1}, a_{l_i + (j-1)K_i})
$$
Update $ A $ in-place.
2. **Type 2 (Range Sum Query)**: Given $ l_i, r_i $:
Compute and output:
$$
\sum_{j=l_i}^{r_i} a_j
$$
**Constraints**
1. $ 3 \leq n, m \leq 2 \times 10^5 $
2. $ 1 \leq a_i \leq 10^9 $
3. For Type 1: $ 1 \leq l_i < r_i \leq n $, $ K_i \in \{2,3\} $, $ K_i \mid (r_i - l_i + 1) $
4. For Type 2: $ 1 \leq l_i \leq r_i \leq n $
**Objective**
For each Type 2 operation, output the sum of the subarray $ A[l_i:r_i] $.