题目背景

小 L 总是在卑微地被强大的人吊打，其中包括小 Y。

题目描述

小 L 和 小 Y 是好朋友。有一天，小 L 拿来了一棵 $n$ 个点的有权值的树。第 $u$ 个点的权值为 $a_u$。但是小 Y 讨厌树，所以二话不说直接把树上的一条边给断了。

小 L 很愤怒，但是为了保持该有礼貌，他决定做好事情后再把这条边连起来。但是，他总是操作失误，导致不但没法连起来，还会有另一条边被断掉。于是，这棵树就被分成了 $3$ 个连通块。

小 Y 看不下去了，于是在割掉边后，开始思考一个对他来说很难的问题。他想知道，在割掉第 $x$ 条边后，由于小 L 还会因为操作失误割掉一条边，则最后所形成的 3 个连通块的权值和的乘积的所有情况的总和 是多少。即设这三个连通块分别为 $a,b,c$，求在已经割掉一条边的情况下

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

的总和。

由于愤怒，每次你算好后，小 L 都会对你帮助小 Y 算出的答案不理不顾，于是小 Y 只好把图恢复到原来那棵树，再割掉一条边，你也得再帮助小 Y 算一次，即再进行一次可能不一样的询问。你需要这样帮助小 Y 一共 $q$ 次，即回答 $q$ 个询问。又因为小 L 和小 Y 都很讨厌太大的数，所以请你用输出这个总和对 $99991$ 取模的结果。又因为输出太耗费时间，你只需要输出所有询问的答案对 $99991$ 取模的总和以及异或和即可。

输入格式

第一行两个正整数 $n, q$。

第二行 $n$ 个非负整数代表 $a_{1,2,...,n}$。

后面 $n-1$ 行中，第 $i$ 行两个正整数 $(u,v)$ 代表第 $i$ 条边 $(u,v)$。

后面 $q$ 个正整数，第 $i$ 个代表第 $i$ 次询问所割掉的边。注意，各个询问是独立的。

输出格式

输出一共两行。

第一行输出所有的答案对 $99991$ 取模后的和（注意，最终输出可能大于等于 $99991$）。

第二行输出所有的答案对 $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

提示

样例说明

对于样例一的第一个询问。已经割掉了第一条边（即边 $(1,2)$）。若小 L 再割掉的边是 $(2,3)$，那么 3 个连通块的权值和的乘积为 $1\times 2\times (3+4)=14$。若小 L 再割掉的边是 $(3,4)$，那么 3 个连通块的权值和的乘积为 $1\times (2+3)\times 4=20$。所以输出为 $14+20=34$。

对于样例一的第二个询问。已经割掉了第二条边（即边 $(2,3)$）。若小 L 再割掉的边是 $(1,2)$，那么 3 个连通块的权值和的乘积为 $1\times 2\times (3+4)=14$。若小 L 再割掉的边是 $(3,4)$，那么 3 个连通块的权值和的乘积为 $(1+2)\times 3\times 4=36$。所以输出为 $14+36=50$。

同理，我们可以求出样例一的第三个询问，答案为 $20+36=56$。

所以三个答案的总和是 $140$，异或和是 $40$。

---

数据规模

$\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) }$ 没有特殊限制。

对于全部数据，满足 $2 \le n, q \le {10}^6$，$0 \le a_i \le {10}^6$。

---

idea by lgswdn
tested by LHQing, Karry5307