{"raw_statement":[{"iden":"statement","content":"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.\n\nAn 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$).\n\nWhen Setsuna $K$-Shift the array $A$, the following events will happen in order:\n\nFor 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}$.\n\nNow, you have an array $A$ of length $n$ ($1$-indexed). Setsuna will perform two kinds of operations on it:\n\nThe 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.\n\nThe second line contains $n$ integers $a_1, a_2, \\\\\\\\cdots, a_n (1 <= a_i <= 10^9)$.\n\nThe $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.\n\nOutput the answer to the corresponding operation $2$ in each line.\n\nAfter the first operation, ${1, 2, 3, 4, 5, 6}$ will become ${2, 1, 4, 3, 5, 6}$.\n\nThe sum of elements of indexes in $[ 2, 3 ]$ is $1 + 4 = 5$.\n\nAfter the third operation, ${2, 1, 4, 3, 5, 6}$ will become ${1, 4, 2, 5, 6, 3}$.\n\nThe sum of elements of indexes in $[ 2, 6 ]$ is $4 + 2 + 5 + 6 + 3 = 20$.\n\n"},{"iden":"input","content":"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."},{"iden":"output","content":"Output the answer to the corresponding operation $2$ in each line."},{"iden":"note","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a 1-indexed array of integers.  \nLet $ m $ be the number of operations.  \n\n**Operations**  \nTwo types of operations are defined:  \n\n1. **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) $:  \n   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 $.  \n   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:  \n   $$\n   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})\n   $$  \n   Update $ A $ in-place.  \n\n2. **Type 2 (Range Sum Query)**: Given $ l_i, r_i $:  \n   Compute and output:  \n   $$\n   \\sum_{j=l_i}^{r_i} a_j\n   $$  \n\n**Constraints**  \n1. $ 3 \\leq n, m \\leq 2 \\times 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^9 $  \n3. For Type 1: $ 1 \\leq l_i < r_i \\leq n $, $ K_i \\in \\{2,3\\} $, $ K_i \\mid (r_i - l_i + 1) $  \n4. For Type 2: $ 1 \\leq l_i \\leq r_i \\leq n $  \n\n**Objective**  \nFor each Type 2 operation, output the sum of the subarray $ A[l_i:r_i] $.","simple_statement":"You are given an array of length n. You need to support two operations:\n\n1. For a range [l, r], divide it into blocks of size K, and rotate each block left by 1 (first element goes to the end).\n2. Query the sum of elements in range [l, r].\n\nK is always 2 or 3, and the block size (r-l+1) is always divisible by K.","has_page_source":false}