Descripción

Se le da una matriz ~A~ de ~N~ enteros ~A_1, ..., A_N~ y un número entero ~K~. Debe procesar ~Q~ consultas de dos tipos siguientes:

-1 ~i_1 i_2 ... i_K~ : debe permutar circularmente ~A_{i1}, ..., A_{iK}~ hacia la izquierda. Así, los nuevos valores de elementos ~A_{i1}, A_{i2}, ..., A_{iK-1}, A_{iK}~ serán ~A_{i2}, A_{i3}, ..., A_{iK}, A_{i1}~. Obsérvese que ~i_1, ..., i_k~ son distintos y no necesariamente en orden creciente.

-2 ~l~ ~r~ ~m~: hay que sumar los elementos de todas las subsecuencias continuas de longitud ~m~ de la secuencia ~A_l, A_{l+1}, ..., A_{r-1}, A_r~.

Nótese que un elemento que aparece en varias subsecuencias debe sumarse varias veces.

Entrada

La primera línea de la entrada contiene dos enteros, ~N~ y ~K~.

La segunda línea contiene ~N~ enteros: los elementos de la matriz ~A~.

La tercera línea contiene un entero ~Q~, el número de consultas, y las siguientes ~Q~ líneas que pueden ser de uno de los dos tipos descritos anteriormente.

Salida

La salida consiste en la respuesta a las consultas del tipo 2, cada respuesta en una nueva línea

Restricciones

• ~0 \le A_i \le 10^6~

• ~1 \le l \le r \le N~

• ~1 \le m \le r - l + 1~

Subtaras

1. 36 puntos, para ~1 \le N, Q \le 10 000, K = 1~
2. 56 puntos, para ~10001 \le N~, ~Q \le 100 000~, ~K = 1~
3. 8 puntos, para ~1 \le N~, ~Q \le 100 000~, ~2 \le K \le 10~

Ejemplo de Entrada

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

Ejemplo de Salida

52
50

Explicaciones

La primera consulta es de tipo ~2~ y debemos calcular la suma de elementos de todas las subsecuencias continuas de longitud ~m = 4~ de la sucesión (~2, 5, 1, 9, 3, 4~). Estas subsecuencias son (~2, 5, 1, 9~), (~5, 1, 9, 3~), (~1, 9, 3, 4~), y la suma de sus elementos es ~52~.

La segunda consulta es de tipo ~1~ y requiere la permutación circular de elementos de la matriz ~A~, situados en los índices ~2, 5, 8~. Así, la matriz ~A~ se convertirá en (~7, 9, 5, 1, 6, 3, 4, 2~).

La tercera consulta es de tipo ~2~ y debemos calcular la suma de elementos de todas las subsecuencias continuas de longitud ~m = 3~ de la secuencia (~9, 5, 1, 6, 3, 4~). Estas subsecuencias son (~9, 5, 1~), (~5, 1, 6~), (~1, 6, 3~), (~6, 3, 4~), y la suma de sus elementos es ~50~.