Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Back to Back

By msabeer · Limits 2s, 512 MB

You will be given an array AA of size NN and QQ queries.

The queries will be given in the following form:

  • 1 L R\text{\textbf{1 L R}}: You have to print the maximum sub-array sum from LthL^{th} index to RthR^{th} index (inclusive) of the array. That means, you need to print MAX(k=ijA[k])MAX(\sum_{k = i}^{j} A[k]) where, LijRL\le i\le j \le R. You can't select empty sub-array.
  • 2 L R X\text{\textbf{2 L R X}}: You have to make XX left circular shift of the values in the range [L,R][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][1, 2, 3, 4, 5] will be [2,3,4,5,1][2, 3, 4, 5, -1].

Input

The first line will contain an integer TT, the number of test cases. Then, the first line of each test case will contain an integer NN, the size of the array AA and the next line will contain the array. After that, there will be an integer QQ, the number of queries followed by QQ queries as explained above.

Constraints:

  • 1T1031 \le T \le 10^3
  • 1N1051 \le N \le 10^5
  • 1Q1051 \le Q \le 10^5
  • 1LRN1 \le L \le R \le N
  • 0XRL+10 \le X \le R - L + 1
  • Ai105 |A_i| \le 10^5
  • The sum of NN will be 105\le 10^5 over all the test cases
  • The sum of QQ will be 105\le 10^5 over all the test cases

Output

For each test case, print "Case #Y:" (without quotes) in the first line where YY is the case number. Then for each query type 1, print the answer in a new line.

Sample

InputOutput
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

    Discussion

    Statistics


    75% Solution Ratio

    BigBagEarliest, 9M ago

    solaimanopeFastest, 0.4s

    BigBagLightest, 10 MB

    mahdi.hasnatShortest, 5157B

    Submit

    Login to submit

    Editorial

    Finding subarray maximum is a very common problem. With value updates in specific positions, it can ...

    Related Contests