2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

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:

1. From the beginning of $A$, every consecutive $K$ elements are divided into a group, so there will be exactly $\frac{|A|}{K}$ groups.
2. In every group, Setsuna does a left circular shift (i.e., the first element in the group will be the last one, and the second element in the group will be the first one, and so on…).

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:

1. Choose an interval $[l,r]$ and an integer $K$, and $K$-Shift the subinterval $\{a_l,a_{l+1},\cdots ,a_r\}$. It is guaranteed that $(r-l+1)$ is a multiple of $K$.
2. Choose an interval $[l,r]$ and ask the value of $\sum _{i=l}^r{a}_i$.