AddK

정수 $N$개로 이루어진 배열 $A$와 정수 $K$가 주어진다. $A$는 $A_1, \dots, A_N$이다. 다음 두 종류의 질의 $Q$개를 처리해야 한다.

• $1 \, i_1 \, i_2 \, \dots \, i_K$: $A_{i_1}, \dots, A_{i_K}$를 왼쪽으로 순환 이동한다. 즉, $A_{i_1}, A_{i_2}, \dots, A_{i_{K-1}}, A_{i_K}$의 값은 각각 $A_{i_2}, A_{i_3}, \dots, A_{i_K}, A_{i_1}$이 된다. $i_1, \dots, i_K$는 서로 다르며, 반드시 증가하는 순서일 필요는 없다.
• $2 \, l \, r \, m$: 수열 $A_l, A_{l+1}, \dots, A_{r-1}, A_r$에서 길이가 $m$인 모든 연속 부분수열의 원소 합을 구한다. 여러 부분수열에 등장하는 원소는 등장한 횟수만큼 더한다.

첫째 줄에 정수 $N$과 $K$가 주어진다. 둘째 줄에 배열 $A$의 원소 $N$개가 주어진다. 셋째 줄에 질의의 개수 $Q$가 주어지고, 이어서 $Q$개의 줄에 위에서 설명한 두 종류 중 하나의 질의가 주어진다.

2번 질의의 답을 한 줄에 하나씩 출력한다.

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

첫 번째 질의는 2번 질의이고, 수열 $(2, 5, 1, 9, 3, 4)$에서 길이가 $m = 4$인 모든 연속 부분수열의 원소 합을 구해야 한다. 부분수열은 $(2, 5, 1, 9)$, $(5, 1, 9, 3)$, $(1, 9, 3, 4)$이고, 원소 합은 52이다.

두 번째 질의는 1번 질의이고, 배열 $A$에서 인덱스 $2$, $5$, $8$에 있는 원소를 왼쪽으로 순환 이동해야 한다. 그러면 배열 $A$는 $(7, 9, 5, 1, 6, 3, 4, 2)$가 된다.

세 번째 질의는 2번 질의이고, 수열 $(9, 5, 1, 6, 3, 4)$에서 길이가 $m = 3$인 모든 연속 부분수열의 원소 합을 구해야 한다. 부분수열은 $(9, 5, 1)$, $(5, 1, 6)$, $(1, 6, 3)$, $(6, 3, 4)$이고, 원소 합은 $50$이다.