Time Limit: 1000 MS    Memory Limit: 65536 K 


Description

Windy has a sequence with N integers. A0 A1 A2 ... AN-1 Windy is a crazy boy, and he want to do M operations in the sequence. (1) C i j ( 0 <= i <= N-1 , 0 <= j <= 109) Change Ai to j, after this operation Ai=j. (2) Q i j ( 0 <= i < j <= N-1 ) Question the max(Ap-Aq) ( i <= p < q <= j )

Input

The first line of input is the number of test case. For each test case: The first line contains two integers N and M. The second line contains N integers Ai. The next M lines each contains "C i j" or "Q i j". There is a blank line before each test case. 1 <= N <= 1000 1 <= M <= 2000 0 <= Ai <= 109

Output

Output the answer for each question on a single line.

Sample Input

3 5 3 0 1 2 3 4 Q 1 3 C 1 10 Q 1 3 5 3 5 2 1 7 3 Q 0 3 C 3 0 Q 0 3 5 1 5 2 1 7 4 Q 0 4

Sample Output

-1 8 4 5 4

Source

8th SCUPC

Author

windy7926778