Time Limit: 3000 MS Memory Limit: 65536 K

## Description

Windy has a sequence with N integers.
A_{0} A_{1} A_{2} ... A_{N-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 <= 10^{9})
Change A_{i} to j, after this operation A_{i}=j.
(2) Q i j
( 0 <= i < j <= N-1 )
Question the max(A_{p}-A_{q}) ( 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 A_{i}.
The next M lines each contains "C i j" or "Q i j".
There is a blank line before each test case.
1 <= N <= 50000
1 <= M <= 100000
0 <= A_{i} <= 10^{9}
## 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