You will be given an array A of size N and Q queries.
The queries will be given in the following form:
1 L R: You have to print the maximum sub-array sum from Lth index to Rth index (inclusive) of the array. That means, you need to print MAX(∑k=ijA[k]) where, L≤i≤j≤R. You can't select empty sub-array.
2 L R X: You have to make X left circular shift of the values in the range [L,R]. For this problem, a left circular shift means removing the first element from the sub-array and inserting it at the end of the sub-array after changing its sign. For example, one left circular shift of a sub-array [1,2,3,4,5] will be [2,3,4,5,−1].
The first line will contain an integer T, the number of test cases. Then, the first line of each test case will contain an integer N, the size of the array A and the next line will contain the array. After that, there will be an integer Q, the number of queries followed by Q queries as explained above.
The sum of N will be ≤105 over all the test cases
The sum of Q will be ≤105 over all the test cases
For each test case, print "Case #Y:" (without quotes) in the first line where Y is the case number. Then for each query type 1, print the answer in a new line.