시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB306541.667%

문제

You are given an array $A$ of $N$ integers $A_1, \dots , A_N$ and an integer $K$. You must process $Q$ queries of the following two types:

  • $1 \, i_1 \, i_2 \, \dots \, i_K$: you must circularly permute $A_{i_1} , \dots , A_{i_K}$ to the left. Thus the new values of elements $A_{i_1} , A_{i_2} , \dots , A_{i_{K-1}} , A_{i_K}$ will be $A_{i_2} , A_{i_3} , \dots , A_{i_K} , A_{i_1}$. Note that $i_1, \dots , i_k$ are distinct and not necessarily in increasing order.
  • $2 \, l \, r \, m$: you must sum the elements of all continuous subsequences with length $m$ from the sequence $A_l , A_{l+1}, \dots , A_{r-1}, A_r$. Note that an element that appears in multiple subsequences must be added multiple times.

입력

The first line of the input contains two integers, $N$ and $K$. The second line contains $N$ integers: the elements of array $A$. The third line contains an integer $Q$, the number of queries, and next $Q$ lines consists of queries, which can be one of two types described above.

출력

The output consists of the answer to the queries of type $2$, every answer on a new line.

제한

  • $0 ≤ A_i ≤ 10^6$
  • $1 ≤ l ≤ r ≤ N$
  • $1 ≤ m ≤ r - l + 1$

서브태스크

번호배점제한
136

$1 ≤ N, Q ≤ 10\,000$, $K = 1$

256

$10\,001 ≤ N, Q ≤ 100\,000$, $K = 1$

38

$1 ≤ N, Q ≤ 100\,000$, $2 ≤ K ≤ 10$

예제 입력 1

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

예제 출력 1

52
50

힌트

The first query is of type $2$ and we must calculate the sum of elements of all continuous subsequences with length $m = 4$ from sequence $(2, 5, 1, 9, 3, 4)$. These subsequences are $(2, 5, 1, 9)$, $(5, 1, 9, 3)$, $(1, 9, 3, 4)$, and the sum of their elements is 52.

The second query is of type $1$ and requires the circular permutation of elements from array $A$, situated at indexes $2$, $5$, $8$. So, the array $A$ will become $(7, 9, 5, 1, 6, 3, 4, 2)$.

The third query is of type $2$ and we must calculate the sum of elements of all continuous subsequences with length $m = 3$ from sequence $(9, 5, 1, 6, 3, 4)$. These subsequences are $(9, 5, 1), (5, 1, 6), (1, 6, 3), (6, 3, 4)$, and the sum of their elements is $50$.

채점 및 기타 정보

  • 예제는 채점하지 않는다.