K-Chunk Sums Queries

You are given an array of n integers and m operations. In addition, you are provided an integer k. The operations are of two types:

• Update Operation: This operation is represented by "1 i v" where you should update the i-th element of the array (1-indexed) to the new value v.
• Query Operation: This operation is represented by "2". For each query, you need to compute the smallest and largest sum among all contiguous subarrays (or k-chunks) of length k in the current state of the array.

Formally, for each query, if the contiguous subarray starting at index j (0-indexed) is given by \(a_j, a_{j+1}, \ldots, a_{j+k-1}\) (for \(0 \le j \le n-k\)), let its sum be \(S_j\). You are required to output:

[ S_{min} = \min_{0 \le j \le n-k} S_j, \quad S_{max} = \max_{0 \le j \le n-k} S_j ]

It is guaranteed that k is less than or equal to n. Process all operations in the order given and for each query operation, output the corresponding results.

inputFormat

The first line contains three integers n, m, and k where:

• n is the number of elements in the array.
• m is the number of operations.
• k is the length of subarray to consider for queries.

The second line contains n space-separated integers representing the initial array.

The next m lines each represent an operation. An update operation is given by: 1 i v and a query operation is given by: 2.

outputFormat

For each query operation, output a line with two integers separated by a space. The first integer is the smallest sum \(S_{min}\) and the second integer is the largest sum \(S_{max}\) among all contiguous subarrays of length k.

## sample

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

6 11
10 15

</p>