Kingdom Security

The kingdom consists of N cities connected by roads forming a tree. Each city in the kingdom has an initial security level. There are two types of queries:

• Update Query (U): Increase the security levels by a given value x along the unique path between two specified cities u and v. If the path contains the cities \( u, \ldots, v \), then each city's security level along this path is increased by \( x \).
• Maximum Query (M): Determine the maximum security level along the unique path from city u to city v (inclusive).

You are given the initial security levels and the list of roads. The tree is undirected and connected, and queries are processed sequentially, meaning that updates can affect subsequent queries.

For a reinforcement (update) query, if the path from \( u \) to \( v \) is defined as \( P(u, v) \), then the security level for every city \( i \) on \( P(u, v) \) is updated as follows:

\[ a_i := a_i + x, \quad \forall \; i \in P(u, v) \]

The maximum query asks you to output the value \( \max_{i \in P(u,v)} a_i \).

inputFormat

The input is given via stdin and has the following format:

1. The first line contains two integers \( N \) and \( Q \), where \( N \) is the number of cities and \( Q \) is the number of queries.
2. The second line contains \( N \) integers: \( a_1, a_2, \ldots, a_N \), representing the initial security levels of the cities.
3. The next \( N-1 \) lines each contain two integers \( u \) and \( v \), indicating that there is a bidirectional road connecting city \( u \) and city \( v \).
4. The following \( Q \) lines each describe a query. A query starts with a character:
   • If the character is U, it is followed by three integers \( u \), \( v \), and \( x \), representing an update query to add \( x \) to each city along the path from \( u \) to \( v \).
   • If the character is M, it is followed by two integers \( u \) and \( v \), representing a query to report the maximum security level along the path from \( u \) to \( v \).

outputFormat

For each query of type M, output the maximum security level on a separate line to stdout.

## sample

5 3
5 3 7 9 2
1 2
1 3
3 4
4 5
M 2 4
U 3 5 4
M 1 5

9
13

</p>