Tywin Lannister is a tactical genius. At the heart of his tactical skills, is the way he has organized his armies, and the way he is able to estimate his soldiers' skill-levels, thus helping him make crucial decisions as to whom to dispatch to which areas of the war.

His army is organized in the form of a hierarchy - indeed it is a tree, with him as the root. We say "A has immediate superior B" if A reports directly to B. We further say "A has superior B" if there is a chain of soldiers starting with A, ending with B, and where each soldier reports directly to the next soldier of the chain. Further, each soldier is assigned an initial skill-level based on prior experience and battle proficiency.

In order for Tywin to decide whom to send to which battle, he has the following scheme: He chooses a particular soldier S as the leader of his temporary 'regiment', and sends in to battle, S as well as all the soldiers that have S as one of their superiors. He estimates the skill level of the regiment as the total skill level of all the soldiers under S (denoted by query "Q S").

After a battle, he may want to update the skill levels of some soldiers. If he wants to update the skill level of soldier S to value x, it is denoted by the query "U S x".

You are given the structure of the army, whose size is N, the initial skill levels of all the individual soldiers, as well the number of queries M. For each query of the type "Q S", report the sum of skill-levels of all the soldiers who have S as their superior.

Note: The soldiers are numbered 1 to N, and Tywin is given the number 1.

Input

The first line consists of the integers N and M, denoting the number of soldiers and the number of queries.

This is followed by a single line consisting of N nonnegative values - the skill levels of the N soldiers.

This is then followed by N-1 lines consisting of pairs of integers (u, v), denoting that either u is an immediate superior of v, or vice-versa.

Finally you are given the M queries, of either the form "U S x" or "Q S".

Output

For each "Q S" query, output the sum of skill values of all the soldiers under S.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 10⁵
• All skill values given with be in the range [0, 20,000]
• 1 ≤ S ≤ N for all queries
• All soldiers will have soldier 1 (Tywin) as their superior

Example

Input:
5 8
7 2 0 5 8
1 2
2 3
2 4
1 5
Q 1
Q 2
U 2 4
Q 1
Q 2
U 5 3
Q 1
Q 2

Output:
22
7
24
9
19
9

For an illustration, let us consider the following tree:

   1
  / \
 2   5
    / \
   3   6
    \
     4


From the above, I can form a bracketed expression of the form:
(x1 + (x2) + (x5 + (x3 + (x4)) + (x6))) Whenever I go down the tree, I am opening a bracket, whenever I go up the tree, I am closing a bracket. I am also giving "variables" that will correspond to skill-values for each node.

Seeing the above, I can rewrite 1,2,3,4,5 by mapping them to values as seen from left to right:
1 -> 1
2 -> 2
5 -> 3
3 -> 4
4 -> 5
6 -> 6

Now, in the mapped version, the bracketed expression looks like:
(y1 + (y2) + (y3 + (y4 + (y5)) + (y6)))

We are here interested in queries of two types:
Type1: change value of x[i], or in other words, y[mapped(i)]
Type2: Find the total in the complete bracket "defined" by i, which is y[mapped(i)] + y[mapped(i)+1] + ... + y[end_range(i)], for suitable mapped(i) and end_range(i).

The good thing to note is, type2 is now a query over values in a range. This can be done by a segment tree or a binary indexed tree! We only need what the range is, given each vertex.

Finding out the range, as well as the mapping, can be done easily by dfs-times. The dfs-time for a node is the value of a time-counter when that node was visited. Indeed, if you ran a dfs on the given tree, it will visit the nodes in the order "1-2-5-3-4-6" itself! The range is then just starting from the current point, and ending at the latest time a node was visited. This information can be returned in the dfs function, as in the following pseudocode:
int dfs(node v, int time)
    mapping[v] = time
    ret = time
    for(c is a child of v)
        ret = dfs(c, ret+1) //give it the next "time"-point, and get the latest time point of the child for future
    begin_range[v] = time
    end_range[v] = ret
    return ret

Calling the above with dfs(1, 1) will do all the magic for you!

Finally, a BIT pseudocode implementation of the rest of the problem:
void update(int S, int x)
    BIT.increment(mapping[S], x - skill[S])
    skill[S] = x;

int query(int S)
    return BIT.query(end_range[S]) - BIT.query(begin_range[S]-1)


Alternate Approach:

This approach was used by some contestants. It is summarized as follows:

Step 1: Perform a heavy-light decomposition of the tree.
Step 2: Initialize each node with the value that is the sum of the skill-levels of its subtree.
Step 3: For each "U S x" query, add "skill[S]-x" to the nodes along the path from S to the root. Due to Heavy-light decomposition structure, this can be done in O(logN ^ 2) time. Also update the value of skill[S].
Step 4: For each "Q S" query, return the value stored in the node S.







My implementation with a segment tree



#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

#define ff first

#define ss second

#define mp make_pair

list<int> sup[100010];

long long int val[100010];

bool visited[100010];

long long int arr[100010];

int top=0;

long long int sttime[100010];

long long int endtime[100010];

long long int vis=0;

long long int  t[1000100];




void build(int node, int a, int b)

{

 if(a>b) return;

 if (a==b)

 {

  t[node]=arr[a];

  return;

 }

 

 build(node*2, a, (a+b)/2);

 build(node*2+1,(a+b)/2+1,b);

 

 t[node]=t[node*2]+t[node*2+1];

}




long long int  query(int node, int a, int b, int i, int j)

{

 if(a>b||a>j||b<i) return 0;

 

 if (a>=i && b<=j) return t[node];

 

 int q1=query(node*2, a, (a+b)/2, i, j);

 int q2=query(node*2+1, (a+b)/2+1, b, i, j);

 

 return q1+q2;

}




void update(int node, int a, int b, int i, int j, long long int inc)

{

 if(a>b) return;

 

 if(a>b||a>j||b<i) return;

 

 if (a>=i && b<=j)

 {

  t[node]=inc;

  

  return;

 }

 

 update(node*2, a, (a+b)/2, i, j, inc);

 update(node*2+1, (a+b)/2+1, b,i, j, inc);

 t[node] = t[node*2] + t[node*2+1];

}

void dfs(int st)

{

 //cout<<"called "<<st<<" tm "<<vis<<endl;

     list<int> ::iterator it;

     arr[vis]=val[st];  

     sttime[st]=vis;

     visited[st]=1;

     for( it=sup[st].begin();it!=sup[st].end();it++)

     {

      if(visited[*it]==0)

      {

            vis++;

     visited[*it]=1;  

     dfs(*it);

     

    }

     }

   //  cout<<"enfing "<<st<<" with "<<vis<<endl;

     endtime[st]=vis;

}

int main()

{

 int n;

 cin>>n;

 int q;

 cin>>q;

 for(int i=0;i<n;i++)

 {

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

 }

 

 for(int i=0;i<n-1;i++)

 {

  int a,b;

  scanf("%d %d",&a,&b);

  a=a-1;

  b=b-1;

  //cout<<" a and b "<<a<<" "<<b<<endl;

  sup[a].push_back(b);

  sup[b].push_back(a);

 }

// cout<<sup[0].size()<<endl;

// cout<<"size "<<endl;

  visited[0]=1;

 dfs(0);




 //cout<<"done "<<endl;

/* for(int i=0;i<n;i++)

 {

  cout<<arr[i]<<" ";

 }

 cout<<endl;

 for(int i=0;i<n;i++)

 {

  cout<<sttime[i]<<" ";

 }

 cout<<endl;

 for(int i=0;i<n;i++)

 {

  cout<<endtime[i]<<" ";

 }

 cout<<endl;*/

 

 build(1,0,n-1);

 //cout<<endl;

 char str[5];

 while(q--)

 {

  int node;long long int  val;

  scanf("%s",str);

  if(str[0]=='Q')

  {

   cin>>val;

   val--;

   int qs,qe;

   qs=sttime[val];

   qe=endtime[val];

  // cout<<"query "<<qs<<" "<<qe<<endl;

   long long int ans=query(1,0,n-1,qs,qe);

    cout<<ans<<endl;

  }

  else

  {

      cin>>node>>val;

      node--;

      

      int upl=sttime[node];

      int upu=sttime[node];

      update(1,0,n-1,upl,upu,val);

  }

 }

 return 0;

}