1226 - Integers

Time Limit: 2s Memory Limit: 128MB

Submissions: 63 Solved: 5
Description
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.
Sample Input
1
5 5
1 2 3 4 5
Q 1 3
C 2 5
Q 1 3
C 5 6
Q 1 5

Sample Output
2
4
5
Hint
Source
ACman(Problem&Datas),Sempr(Special Datas), HUST Programming Contest 2007