Tree Chain Decomposition and Weight Computation

Given a tree with n nodes, the leaf nodes hold an integer value and every non‐leaf node contains an operator (+ or *). First perform a heavy‐light (tree chain) decomposition on the tree. In case of ties in subtree sizes, choose the child with the smaller index as the heavy child.

For each node, we define its weight V_i in the following way:

• If node i is a leaf, then V_i equals its given value (mod 99991).
• If node i is non‐leaf and its operator is denoted by C_i, let D_i be the set of all its children. Suppose node i lies in some heavy chain P_i. For every child k ∈ D_i that is not on the same chain as i (i.e. not the heavy child), let the heavy chain beginning at k be P_k. Define the set $$Charge_i = \bigcup_{k\in D_i,\, k\notin P_i} P_k.$$

  Then the weight of node i is computed as follows:

</p>

$$V_i= \begin{cases}\sum_{j\in Charge_i}V_j \quad &\text{if}\; C_i = +,\\[8pt] \prod_{j\in Charge_i}V_j \quad &\text{if}\; C_i = \times. \end{cases}$$

If a non‐leaf node does not have any child outside its chain (i.e. Chargei is empty), then it is ignored in the sense that its weight is taken as the identity: 0 for a + operator and 1 for a * operator.

You need to support the following three operations:

1. Update the value of a leaf node.
2. Update the operator of a non‐leaf node (to either + or *).
3. Query: Given any node, obtain the aggregate sum and product (mod 99991) of the weights of all nodes in the heavy chain to which this node belongs.

Note: The tree structure is fixed. A heavy chain is defined by the heavy‐light decomposition. For every node not chosen as a heavy child, a new chain is started. All computed weights should be taken modulo 99991.

inputFormat

The input begins with two integers n and q (number of nodes and number of operations), separated by a space.

The next line contains n tokens. For node i (1-indexed):
- If the token is an integer, then node i is a leaf with that value.
- If the token is + or *, then node i is a non‐leaf with that operator.

Then follow n-1 lines each containing two integers u v indicating an edge between nodes u and v. The tree is rooted at node 1.

Finally, there are q lines, each describing an operation. The operations are in one of the following formats:

• 1 u x: Update the value of leaf node u to integer x.
• 2 u op: Update the operator of non‐leaf node u to op (either + or *).
• 3 u: Query the heavy chain containing node u. (See below for details.)

outputFormat

For each operation of type 3, output two integers separated by a space on a separate line: the first is the sum and the second is the product (both modulo 99991) of the weights of all nodes in the heavy chain containing the queried node.

sample

5 5
+ 5 + 3 7
1 2
1 3
3 4
3 5
3 1
1 2 10
3 2
2 3 *
3 3

15 105
10 10
20 210

</p>