Nowadays, ACman is studying a very useful book named Discrete Mathematics. One day, he read some articles about integers, and he thought out another interesting problems. Given you N integers, {A1,A2,...,AN}. You need to deal with two kinds of operations. One type of the operations is to change some integer in a given position, and the other is to query the difference between the maximum and the minimum in a given interval.
Input
The first line of input is an integer giving number of cases to follow. For each case:
The first line contains two numbers N(1<N<100000) and Q(1<Q<100000).
The second line contains N numbers, the initial values of {A1,A2,...,AN}.
Each of the next Q lines represents an operation.
“C a b” means changing the value of Aa into b.
“Q a b” means querying the difference between maximum and minimum of the interval, {Aa,Aa+1,...,Ab-1,Ab}.
Output
You need to answer all Q operations in order. There is only one answer in a line.