Description

Little L and Little Y are good friends. One day, Little L brought a weighted tree with $n$ vertices. The weight of vertex $u$ is $a_u$. However, Little Y hates trees, so without saying anything, he directly cut one edge of the tree.

Little L was very angry, but in order to stay polite, he decided to reconnect this edge after finishing his work. However, he always makes mistakes in his operations: not only can he not reconnect it, but he will also cut another edge. As a result, the tree is split into $3$ connected components.

Little Y could not stand it anymore. After cutting an edge, he started thinking about a difficult problem for him. He wants to know: after cutting the $x$-th edge, since Little L will still mistakenly cut one more edge, what is the sum over all possible cases of the product of the sums of weights of the 3 connected components formed in the end. That is, let the three connected components be $a, b, c$. Given that one edge has already been cut, compute the total sum of

$$(\sum_{u\in a} a_u)\times (\sum_{u\in b} a_u) \times (\sum_{u\in c} a_u)$$

over all possibilities of the second cut.

Because of his anger, every time you finish the calculation, Little L ignores the answer you computed for Little Y. So Little Y has to restore the graph back to the original tree, cut another edge, and you must help Little Y compute it again, i.e., perform another (possibly different) query. You need to help Little Y for a total of $q$ times, meaning you must answer $q$ queries. Also, because both Little L and Little Y dislike very large numbers, please output this total sum modulo $99991$. Also, because printing is too time-consuming, you only need to output the sum and the xor-sum of the answers (each taken modulo $99991$) over all queries.

Input Format

The first line contains two positive integers $n, q$.

The second line contains $n$ non-negative integers representing $a_{1,2,...,n}$.

In the following $n-1$ lines, the $i$-th line contains two positive integers $(u, v)$, representing the $i$-th edge $(u, v)$.

Then there are $q$ positive integers. The $i$-th integer represents the edge cut in the $i$-th query. Note that all queries are independent.

Output Format

Output two lines in total.

The first line outputs the sum of all answers modulo $99991$ (note that the final output may be greater than or equal to $99991$).

The second line outputs the xor-sum of all answers modulo $99991$.

4 3
1 2 3 4
1 2
2 3
3 4
1
2
3

140
40

7 2
1 1 1 1 1 1 1
1 2
1 3
2 6
2 4
1 5
3 7
2
6

70
52

Hint

Sample Explanation

For the first query of Sample 1, the first edge (i.e., edge $(1, 2)$) has already been cut. If Little L cuts edge $(2, 3)$ again, then the product of the sums of weights of the 3 connected components is $1\times 2\times (3+4)=14$. If Little L cuts edge $(3, 4)$ again, then the product is $1\times (2+3)\times 4=20$. So the output is $14+20=34$.

For the second query of Sample 1, the second edge (i.e., edge $(2, 3)$) has already been cut. If Little L cuts edge $(1, 2)$ again, then the product is $1\times 2\times (3+4)=14$. If Little L cuts edge $(3, 4)$ again, then the product is $(1+2)\times 3\times 4=36$. So the output is $14+36=50$.

Similarly, we can compute the third query of Sample 1, whose answer is $20+36=56$.

So the total sum of the three answers is $140$, and the xor-sum is $40$.

---

Constraints

$\texttt{Subtask 1 (1 pts) } a_i=0$。
$\texttt{Subtask 2 (5 pts) } n,q\le 300$。
$\texttt{Subtask 3 (14 pts) } n\le 300$。
$\texttt{Subtask 4 (20 pts) } n\le 5000$。
$\texttt{Subtask 5 (10 pts) } u=v-1$。
$\texttt{Subtask 6 (50 pts) }$ No special constraints.

For all data, $2 \le n, q \le {10}^6$ and $0 \le a_i \le {10}^6$.

---

idea by lgswdn
tested by LHQing, Karry5307

Translated by ChatGPT 5