You will be given an array $A$
of size $N$
and $Q$
queries.
The queries will be given in the following form:
$\text{\textbf{1 L R}}$
: You have to print the maximum sub-array sum from $L^{th}$
index to $R^{th}$
index (inclusive) of the array. That means, you need to print $MAX(\sum_{k = i}^{j} A[k])$
where, $L\le i\le j \le R$
. You can't select empty sub-array.$\text{\textbf{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.
$1 \le T \le 10^3$
$1 \le N \le 10^5$
$1 \le Q \le 10^5$
$1 \le L \le R \le N$
$0 \le X \le R - L + 1$
$ |A_i| \le 10^5$
$N$
will be $\le 10^5$
over all the test cases$Q$
will be $\le 10^5$
over all the test casesFor 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.
Input | Output |
---|---|
2 5 10 4 8 7 9 3 2 1 5 2 2 5 5 1 1 1 5 5 11 6 3 10 6 3 2 1 3 1 1 1 3 1 3 4 | Case #1: 24 Case #2: 9 10 |