Back to Back

msabeer Criterion 2020 Round 7
Limits 2s, 512 MB

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]$.

Input

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.

Constraints:

  • $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$
  • The sum of $N$ will be $\le 10^5$ over all the test cases
  • The sum of $Q$ will be $\le 10^5$ over all the test cases

Output

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.

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

Submit

Login to submit.

Statistics

80% Solution Ratio
BigBagEarliest, Sep '20
samiulsamiFastest, 0.3s
samiulsamiLightest, 8.9 MB
samiulsamiShortest, 5075B
Toph uses cookies. By continuing you agree to our Cookie Policy.