很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。 

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input

本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M ( <N<=,<M< )，分别代表学生的数目和操作的数目。

学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。

当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output

对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

Q

U

Q

Q

U

Q  5

Sample Output

Hint

Huge input,the C function scanf() will work better than cin

 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<string.h>

 #include<cmath>

 #include<queue>

 #include<stdlib.h>

 typedef long long ll;

 using namespace std;

 const int N=;

 //5 6

 //1 2 3 4 5

 //Q 1 5    ->5

 //U 3 6

 //Q 3 4    ->6

 //Q 4 5    ->5

 //U 2 9

 //Q 1 5    ->9

 int a[*N];//需要开到四倍空间

 //每个父节点记录的是它下面的两个节点的最大值

 void build(int L,int R,int i)

 {

     if(L==R)

     {

         scanf("%d",&a[i]);

         return;

     }

     int mid=(L+R)>>;

     build(L,mid,i<<);

     build(mid+,R,i<<|);

     a[i]=max(a[i<<],a[i<<|]);//pushup(i)////每次传的时候把根节点也往下去寻找最大值

     ////比较其左右两个节点的大小，取最大值

     //看题目给的需要求什么

 }

 //update(aa,bb,1,n,1)

 //把下标为aa的元素修改成bb，更新节点值，更改节点

 void update(int aa,int bb,int L,int R,int i)

 {

     if(L==R)

     {

         a[i]=bb;

         return;

     }

     int mid=(L+R)>>;

     if(aa<=mid)//不是L<=mid

         update(aa,bb,L,mid,i<<);

     else

         update(aa,bb,mid+,R,i<<|);

     a[i]=max(a[i<<],a[i<<|]);

 }

 //query(aa,bb,1,n,1)

 int query(int left,int right,int L,int R,int i)

 {

     if(left<=L&&right>=R)

         return a[i];

     int mid=(L+R)>>;

     int ans=-;

     if(left<=mid)

         ans=max(ans,query(left,right,L,mid,i<<));

     // else

     if(right>mid)

         ans=max(ans,query(left,right,mid+,R,i<<|));

     return ans;

 }

 int main()

 {

     int n,m;

     while(~scanf("%d %d",&n,&m))

     {

         memset(a,,sizeof(a));

         build(,n,);//传入最左端点，最右端点，根节点进行建树

         //建树的过程中输入每一个节点

 //    for(int i=1;i<=n;i++)

 //        scanf("%d",&a[i]);

         string ss;

         for(int i=; i<m; i++)

         {

             cin>>ss;

             int aa,bb;

             if(ss=="Q")

             {

                 scanf("%d %d",&aa,&bb);

                 printf("%d\n",query(aa,bb,,n,));

             }

             else

             {

                 //把下标为aa的元素修改成bb

                 scanf("%d %d",&aa,&bb);

                 update(aa,bb,,n,);

             }

         }

     }

     return ;

 }