For a sequence S1,S2,⋯,SNS1,S2,⋯,SN, and a pair of integers (i,j)(i,j), if 1≤i≤j≤N1≤i≤j≤N and Si<Si+1<Si+2<⋯<Sj−1<SjSi<Si+1<Si+2<⋯<Sj−1<Sj, then the sequence Si,Si+1,⋯,SjSi,Si+1,⋯,Sj 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 TT, which stands for the number of test cases you need to solve.

Every test case begins with two integers NN, QQ, where NN is the size of the sequence, and QQ is the number of queries. S1,S2,⋯,SNS1,S2,⋯,SN are specified on the next line, and then QQ queries follow. Every query begins with a character a or q. a is followed by three integers LL, RR, VV, meaning that add VV to members in the interval [L,R][L,R] (including LL, RR), and q is followed by two integers LL, RR, meaning that you should output the length of the LCIS of interval [L,R][L,R].

T≤10T≤10;

1≤N,Q≤1000001≤N,Q≤100000;

1≤L≤R≤N1≤L≤R≤N;

−10000≤S1,S2,⋯,SN,V≤10000−10000≤S1,S2,⋯,SN,V≤10000.

Output

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

Sample Input

15 60 1 2 3 4 q 1 4a 1 2 -10a 1 1 -6a 5 5 -4q 2 3q 4 4

Sample Output

Case #1:421 线段树维护各个左闭右开区间。需要注意的是区间合并的条件，为方便判断，每个结点记录这个区间左右两侧的值，方便进行比较能否合并。每次查询、修改的时候，没完全在目标区间内的时候 不要忘记将之前未传下去的改变传递下去。

1 #include 
     
        2 //#include
      
         3 #include 
       
          4 #include 
        
           5 #include