Three Components Product Sum

Given a weighted tree with n nodes (numbered from 1 to n), where the weight of node u is \(a_u\), you are to answer q queries. The tree has n-1 edges. In each query, an edge is chosen to be cut first, and then due to a mistake another edge will be cut, splitting the tree into 3 connected components.

More precisely, for a given query with an integer \(x\) (1-indexed), let the x-th edge (as given in the input) connecting nodes \(u\) and \(v\) be removed. This removal splits the tree into two connected components. Then, an extra edge (different from the already removed one) is removed from one of these two components. If the extra removal splits a component into two parts with sums of weights \(S_1\) and \(S_2\), and the other component has a total weight of \(S_3\), then the product for this operation is defined as

[ P = S_1 \times S_2 \times S_3. ]

Notice that the extra removal can be any edge present in either of the two components. In other words, if the first removal splits the tree into two components with total weights \(S_u\) and \(S_v\), and for a component \(T\) (with total weight \(S_T\)) we define

[ f(T) = \sum_{e \in T} (\text{sum of one part by removing }e) \times (S_T - \text{that sum}), ]

then the answer for the query is given by

[ \text{ans} = S_v \times f(T_u) + S_u \times f(T_v). ]

For each query, compute \(\text{ans} \bmod 99991\>. After processing all q queries (note that after each query the tree is restored to its original state), output two numbers: the sum (modulo 99991) of all query answers and the bitwise XOR of all query answers.

inputFormat

The first line contains two integers n and q.

The second line contains n integers \(a_1, a_2, \dots, a_n\) representing the weights of the nodes.

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

The following q lines each contain an integer \(x\) (1-indexed) indicating that the x-th edge (in the given order) is removed first.

outputFormat

Output two integers separated by a space: the sum (modulo 99991) of the answers for all queries and the bitwise XOR of the answers for all queries.

sample

3 1
1 2 3
1 2
2 3
1

6 6