Migrated from Lutece 360 Another LCIS

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

For a sequence $S_1,S_2,\ldots ,S_N$, and a pair of integers $(i, j)$, if $1\leq i\leq j\leq N$ and $S_i < S_{i+1} < S_{i+2} <\ldots < S_{j-1} < S_j$, then the sequence $S_i,S_{i+1},\ldots ,S_j$ is a CIS (Continuous Increasing Subsequence). The longest CIS of a sequence is called the LCIS (Longest Continuous Increasing Subsequence).

In this problem, we will give you a sequence first, and then some add operations and some query operations. An add operation adds a value to each member in a specified interval. For a query operation, you should output the length of the LCIS of a specified interval.

Input

The first line of the input is an integer $T$, which stands for the number of test cases you need to solve.

Every test case begins with two integers $N$, $Q$, where $N$ is the size of the sequence, and $Q$ is the number of queries. $S_1,S_2,\ldots ,S_N$ are specified on the next line, and then $Q$ queries follow. Every query begins with a character a or q. a is followed by three integers $L$, $R$, $V$, meaning that add $V$ to members in the interval $[L, R]$ (including $L$, $R$), and q is followed by two integers $L$, $R$, meaning that you should output the length of the LCIS of interval $[L, R]$.

$T\leq 10$;

$1\leq N, Q \leq 100000$;

$1 \leq L \leq R \leq N$;

$-10000\leq S_1,S_2,\ldots ,S_N, V\leq 10000$.

Output

For every test case, you should output Case #k: on a single line first, where $k$ indicates the case number and starts at $1$. Then for every q query, output the answer on a single line. See sample for more details.

Samples

1
5 6
0 1 2 3 4 
q 1 4
a 1 2 -10
a 1 1 -6
a 5 5 -4
q 2 3
q 4 4

Case #1:
4
2
1

Resources

The 9th UESTC Programming Contest Preliminary