Captain America needs to lead his soldiers in his war against the Red Skull. He organized his team in such a way that he can estimate his soldiers’ energy-levels and capacity at any moment, which would help him make crucial decisions as to whom to dispatch to which areas of the war.

He organized his army in the form of a hierarchy - with him as the leader. He set some rules for his war strategy -

1. "A has immediate superior B" if A reports directly to B.
2. "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.
3. Each soldier is assigned an initial energy-level based on prior experience and battle proficiency.

In order for Captain to decide whom to send to which area of the war, he designed the following scheme:

1. He chooses a particular soldier S as the leader of his temporary 'regiment', and sends into battle, S as well as all the soldiers that have S as one of their superiors. He estimates the energy- level of the regiment as the total energy-level of all the soldiers under S (denoted by query "Q S").
2. After the war, he may want to update the energy-levels of some soldiers. If he wants to update the energy-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 energy-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 energy-levels of all the soldiers who have S as their superior.

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

Input Format:

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 energy-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 Format:

For each "Q S" query, output the sum of energy-levels of all the soldiers under S.

Constraints:

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