Back to Back

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

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