== 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{~k~}$ sunt distincte şi nu neapărat in ordine crescătoare.

* $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~}$. Remarcaţi că elementele care apar în mai multe secvenţe vor fi adunate de mai multe ori.

h2. Date de intrare

Fişierul de intrare $addk.in$ ...

Prima linie a fişierul de intrare $addk.in$ conţine două numere întregi, $N$ şi $K$. A doua linie conţine N numere întregi: elementele vectorului $A$. A treia linie conţine un întreg $Q$, numărul de cerinţe, şi apoi $Q$ linii conţinând cerinţele, care pot fi din cele două tipuri descrise mai sus.

h2. Date de ieşire

În fişierul de ieşire $addk.out$ ...

În fişierul de ieşire $addk.out$ trebuie să conţină răspunsurile la cerinţele de tip 2, câte unul pe linie

h2. Restricţii

* $... ≤ ... ≤ ...$

* $0 ≤ A{~i~} ≤ 10^6^$
* $1 ≤ l ≤ r ≤ N$
* $1 ≤ m ≤ r - l + 1$
* În plus:
 
table(restrictii). |_. # |_. %{font-family: Verdana, sans-serif;} Punctaj% |_. %{font-family: Verdana, sans-serif;} Restricţii % |
| $1$ | $36$ | $1 ≤ N,Q ≤ 10 000 , K = 1$ |
| $2$ | $56$ | $10 001 ≤ N,Q ≤ 100 000, K = 1$ |
| $3$ | $8$ | $1 ≤ N,Q ≤ 100 000, 2 ≤ K ≤ 10$ |

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 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

|
h3. Explicaţie

...

Prima cerinţă este de tip $2$ şi trebuie să calculăm suma elementelor tuturor subsecvenţelor de lungime $m = 4$ din secvenţa $2, 5, 1, 9, 3, 4$. Aceste subsecvenţe sunt $(2, 5, 1, 9), (5, 1, 9, 3), (1, 9, 3, 4)$, iar suma elementelor lor este $52$.
 
A doua cerinţă este de tip $1$ şi are ca efect permutarea circulară a elementelor din şirul $A$, situate pe poziţiile $2, 5, 8$. Astfel, şirul $A$ devine $7, 9, 5, 1, 6, 3, 4, 2$.
 
A treia cerinţă este de tip $2$ şi trebuie să calculăm suma elementelor tuturor subsecvenţelor de lungime $m = 3$ din secvenţa $9, 5, 1, 6, 3, 4$. Aceste subsecvenţe sunt $(9, 5, 1), (5, 1, 6), (1, 6, 3), (6, 3, 4)$, iar suma elementelor lor este $50$.

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