== include(page="template/taskheader" task_id="addk") ==

Se consideră un şir $A$ cu $N$ elemente numere naturale $A ~1~,. . ., A ~N~$ si un număr natural $K$. Se cere să se proceseze $Q$ cerinţe de următoarele două tipuri:

Se consideră un şir $A$ cu $N$ elemente numere naturale $A{~1~},. . ., A{~N~}$ si un număr natural $K$. Se cere să se proceseze $Q$ cerinţe de următoarele două tipuri:

* $1 i{~1~} i{~2~},..., i{~K~}$: se permută circular la stânga elementele şirului $A{~i{~1~}~},..., A{~i{~K~}~}$ . Astfel noile valor ale elementelor $A{~i{~1~}~}, A{~i{~2~}~} , ..., A{~i{~K-1~}~} , A{~i{~K~}~}$ vor fi $A{~i{~2~}~} , A{~i{~2~}~} , ..., A{~i{~K~}~} , A{~i{~1~}~}$ . Remarcaţi că $i{~1~}, i{~2~},... , i{~k~}$ sunt distincte şi nu neapărat in ordine crescătoare.

* $2 l r m$:  se cere calculul sumei elementelor tuturor subsecvenţelor continue de lungime $m$ din secvenţa $A{~l~}, A{~l+1~},..., A{~r-1~}, A{~r-2~}$. Remarcaţi că elementele care apar în mai multe secvenţe vor fi adunate de mai multe ori.

* $2 l r m$:  se cere calculul sumei elementelor tuturor subsecvenţelor continue de lungime $m$ din secvenţa $A{~l~}, A{~l+1~},..., A{~r-1~}, A{~r~}$. Remarcaţi că elementele care apar în mai multe secvenţe vor fi adunate de mai multe ori.

h2. Date de intrare

h2. Restricţii

* $0 ≤ A{~i~} ≤ 10{^6^}$

* $0 ≤ A{~i~} ≤ 10^6^$

* $1 ≤ l ≤ r ≤ N$
* $1 ≤ m ≤ r - l + 1$
* În plus:

h2. Exemplu
table(example). |_. addk.in |_. addk.out |

| 8

| 8 3

  7 2 5 1 9 3 4 6
  3
  2 2 7 4