Maximize Remainder in Tree Game

The game is played on a tree with n nodes. Each node i has an associated weight \(w_i\). The tree is given by its n-1 edges.

In each round, the system presents a chain (i.e. a simple path) in the tree. Player A must choose two nodes from this chain with different weights. His score is computed as \(w_x \bmod w_y\) where \(x\) and \(y\) are the two nodes he selects (note that the order matters). Player A will choose a pair that maximizes his own score.

After that, Player B chooses two nodes from the entire tree that were not chosen by Player A. The scoring is the same: if B chooses nodes \(x\) and \(y\) (with \(w_x \neq w_y\)), his score is \(w_x \bmod w_y\). If a valid pair does not exist for any player, the score for that player is \(-1\).

To increase the challenge, the system may also issue an update query that increases the weight of a node.

Your task is to process m queries sequentially on the tree. There are two types of queries:

• Q k x1 x2 ... xk: A chain query. Among the k given nodes (which form a chain), determine the maximum value \(w_x \bmod w_y\) over all pairs of nodes with different weights (this is Player A's score). Then, remove the two nodes chosen by Player A (if no valid pair exists, consider both scores as \(-1\)), and compute Player B's maximum score from the remaining nodes in the tree using the same rule.
• U x d: An update query. Increase the weight of node \(x\) by \(d\), i.e. set \(w_x = w_x + d\).

For chain queries, if multiple pairs yield the maximum remainder for Player A, choose the pair with the smallest lexicographical order (comparing the pair \((x, y)\) as \((\text{first node index}, \text{second node index})\)). Then remove those two nodes when computing Player B's score.

Output, for each chain query, two integers separated by a space: Player A's score and Player B's score.

inputFormat

The first line contains two integers \(n\) and \(m\) — the number of nodes in the tree and the number of queries.

The second line contains \(n\) integers \(w_1, w_2, ..., w_n\) where \(w_i\) is the initial weight of node \(i\).

The next \(n-1\) lines each contain two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\) in the tree.

The following \(m\) lines each describe a query, which can be in one of the following formats:

• Q k x1 x2 ... xk: A chain query with \(k\) nodes. These nodes form a valid chain in the tree.
• U x d: An update query that increases \(w_x\) by \(d\).

outputFormat

For each chain query (queries beginning with Q), output a single line with two space-separated integers: the maximum score of Player A and the maximum score of Player B, computed as described. If a player cannot select a valid pair (i.e. there are not two nodes with different weights), output \(-1\) for that player's score.

sample

5 4
5 2 7 7 3
1 2
1 3
3 4
3 5
Q 3 1 2 3
U 2 3
Q 4 2 3 4 5
Q 2 1 5

5 3
5 5
3 5

</p>