Fleet Management

In this problem, you are tasked with managing a fleet of trucks. Each truck has a load capacity and the trucks are organized in a hierarchical structure where one truck may directly manage several other trucks. Initially, there are (N) trucks labeled from 1 to (N) with specified capacities, and (N-1) relationships describe the direct management (parent-child) relationships between them. You will process a series of queries, each of which can be one of the following types:

1. Query (Q c): Compute the total load capacity of truck (c) and all trucks that are directly or indirectly managed by truck (c). The total capacity is defined by [ S(c)=\text{capacity}(c)+\sum_{child\in\text{subordinates}(c)}S(child)]

2. Update (U p x): Update the load capacity of truck (p) to a new value (x).

3. Addition (A p x c): Introduce a new truck with id (p) and load capacity (x), and designate it as a subordinate of truck (c).

The operations must be performed sequentially as given. All input is read from standard input (stdin) and all output should be sent to standard output (stdout).

inputFormat

The input begins with an integer (N) representing the number of initial trucks. The next line contains (N) space-separated integers which are the initial load capacities of trucks with ids from 1 to (N). Then follow (N-1) lines, each containing two space-separated integers (u) and (v), indicating that truck (u) directly manages truck (v). After that, an integer (Q) is given representing the number of queries to process. The following (Q) lines each describe a query in one of the following formats:

• Q c: Query the total load capacity of truck (c) and all trucks in its subtree. • U p x: Update the load capacity of truck (p) to (x). • A p x c: Add a new truck with id (p) and capacity (x) as a subordinate of truck (c).

outputFormat

For each query of type Q, output a single line containing one integer: the total load capacity of the truck specified in the query along with all the trucks under its management.## sample

5
10 5 8 3 7
1 2
1 3
2 4
2 5
6
Q 1
Q 2
A 6 2 1
U 4 10
Q 1
Q 2

33
15
42
22