Array Rotation and Contiguous Subarray Sum Queries

You are given an array \(A = [A_1, A_2, \dots, A_N]\) of \(N\) integers and an integer \(K\). You need to process \(Q\) operations. There are two types of operations:

• Operation 1: 1 i_1 i_2 \dots i_K \(\rightarrow\) Perform a cyclic rotation on the elements at indices \(i_1, i_2, \dots, i_K\). More formally, update: \[ A_{i_1} = A_{i_2},\quad A_{i_2} = A_{i_3},\quad \dots, \quad A_{i_K} = A_{i_1}. \]
• Operation 2: 2 l r m \(\rightarrow\) For the subarray \(A[l \dots r]\), compute and output the sum of elements for every contiguous subsequence of length \(m\). That is, for every \(i\) with \(l \le i \le r-m+1\), compute \(S_i = \sum_{j=i}^{i+m-1} A_j\) and output them in order separated by spaces.

It is guaranteed that in each operation of type 1, the indices \(i_1, i_2, \dots, i_K\) are pairwise distinct.

inputFormat

The first line of input contains three integers \(N\), \(Q\), and \(K\) separated by spaces.

The second line contains \(N\) integers denoting the array \(A\): \(A_1, A_2, \dots, A_N\).

The following \(Q\) lines each describe an operation in one of the following forms:

• 1 i_1 i_2 ... i_K — A type 1 operation (cyclic rotation).
• 2 l r m — A type 2 operation (query contiguous subarray sums).

outputFormat

For each type 2 operation, output a single line containing the sums of each contiguous subsequence of length \(m\) in the subarray \(A[l \dots r]\), separated by a space.

sample

5 3 3
1 2 3 4 5
2 1 5 2
1 2 3 5
2 2 5 2

3 5 7 9
8 9 6