Cerința

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 i1 i2 ... iK: se permută circular la stânga elementele şirului A[i1], …, A[iK]. Astfel noile valori ale elementelor A[i1], A[i2], …, A[iK-1], A[iK] vor fi A[i2], A[i3], …, A[iK], A[i1]. Remarcaţi că i1, …, iK 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[il], A[il+1], …, A[ir-1], A[ir]. Remarcaţi că elementele care apar în mai multe secvenţe vor fi adunate de mai multe ori.

Date de intrare

Prima linie intrării standard 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.

Date de ieșire

La ecran trebuie să afișați răspunsurile la cerinţele de tip 2, câte unul pe linie.

Restricții și precizări

• 1 ≤ A[i] ≤ 1.000.000
• 1 ≤ l ≤ r ≤ N
• 1 ≤ m ≤ r - l + 1
• pentru 36 de puncte, 1 ≤ N, Q ≤ 10.000 și K = 1
• pentru 56 de puncte, 10.001 ≤ N, Q ≤ 100.000 și K = 1
• pentru 8 de puncte, 1 ≤ N, Q ≤ 100.000 și 2 ≤ K ≤ 10

Exemplu:

Intrare

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

Ieșire

52
50

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.