The Steiner Tree problem is stated as follows:

Given an undirected graph 
𝐺
=
(
𝑉
,
𝐸
)
G=(V,E) with a set of vertices 
𝑉
V and edges 
𝐸
E, and a subset of vertices 
𝑆
⊆
𝑉
S⊆V called terminals, the goal is to find a minimum-weight tree 
𝑇
T (a Steiner tree) that spans all the terminals in 
𝑆
S. This tree may include non-terminal vertices (called Steiner vertices) from 
𝑉
\
𝑆
V\S. The weight of the tree is the sum of weights of its edges.

In this case, we will analyze the node-weighted variation in which the nodes contain the weights instead of the edges so the weight of the tree is the sum of weights of its nodes.

In addition, to make things easier, we will consider that the given graph is a tree (connected undirected acyclic graph).

Now, for every subset 
𝑆
S with size 
𝑘
k, you must compute the weight of its Steiner Tree and sum it up. Since this would be too easy for you, let's consider every 
𝑘
k from 
1
1 to 
𝑁
N. Since this values could be large, compute them modulo 
1
0
9
+
99999
10 
9
 +99999.

Standard input
The first line of input contains an integer 
𝑁
N, the number of nodes in the tree.

The second line of input contains 
𝑁
N integers 
𝑊
𝑖
W 
i
​
 , the 
𝑖
i-th integer is the weight of the 
𝑖
i-th node.

The following 
𝑁
−
1
N−1 lines contain two integers 
𝑈
𝑖
U 
i
​
  and 
𝑉
𝑖
V 
i
​
 , the 
𝑖
i-th line contains the extreme nodes of the 
𝑖
i-th edge.

Standard output
Print 
𝑁
N lines. The 
𝑖
i-th line must contain the sum of all the node-weighted Steiner trees over every subset of nodes with size 
𝑖
i modulo 
1
0
9
+
99999
10 
9
 +99999.

Constraints and notes
2
≤
𝑁
≤
2
∗
1
0
5
2≤N≤2∗10 
5
 .
1
≤
𝑊
𝑖
≤
1
0
9
1≤W 
i
​
 ≤10 
9
  for all 
𝑖
=
1
,
…
,
𝑁
i=1,…,N.
1
≤
𝑈
𝑖
,
𝑉
𝑖
≤
𝑁
,
𝑈
𝑖
≠
𝑉
𝑖
1≤U 
i
​
 ,V 
i
​
 ≤N,U 
i
​
 

=V 
i
​
  for all 
𝑖
=
1
,
…
,
𝑁
−
1
i=1,…,N−1.
It is guaranteed that the given graph is a tree.
Input	Output	Explanation
3
3 2 1
2 3
1 2
6
14
6
In this case, we have the following tree:


It's not hard to notice that the node-weighted Steiner trees of the following subsets are:

𝑆
=
{
1
}
→
𝑇
=
{
1
}
S={1}→T={1} with weight 
3
3.
𝑆
=
{
2
}
→
𝑇
=
{
2
}
S={2}→T={2} with weight 
2
2.
𝑆
=
{
3
}
→
𝑇
=
{
3
}
S={3}→T={3} with weight 
1
1.
𝑆
=
{
1.2
}
→
𝑇
=
{
1
,
2
}
S={1.2}→T={1,2} with weight 
5
5.
𝑆
=
{
1.3
}
→
𝑇
=
{
1
,
2
,
3
}
S={1.3}→T={1,2,3} with weight 
6
6.
𝑆
=
{
2.3
}
→
𝑇
=
{
2
,
3
}
S={2.3}→T={2,3} with weight 
3
3.
𝑆
=
{
1
,
2.3
}
→
𝑇
=
{
1
,
2
,
3
}
S={1,2.3}→T={1,2,3} with weight 
6
6.
Summarizing, the sum of all the node-weighted Steiner trees are:

With size 
1
1 is 
6
6.
With size 
2
2 is 
14
14.
With size 
3
3 is 
6
6
4
10 1 20 40
1 3
2 3
3 4
71
273
233
71
In this case, we have the following tree:


It's not hard to notice that the node-weighted Steiner trees of the following subsets are:

𝑆
=
{
1
}
→
𝑇
=
{
1
}
S={1}→T={1} with weight 
10
10.
𝑆
=
{
2
}
→
𝑇
=
{
2
}
S={2}→T={2} with weight 
1
1.
𝑆
=
{
3
}
→
𝑇
=
{
3
}
S={3}→T={3} with weight 
20
20.
𝑆
=
{
3
}
→
𝑇
=
{
4
}
S={3}→T={4} with weight 
40
40.
𝑆
=
{
1.2
}
→
𝑇
=
{
1
,
2
,
3
}
S={1.2}→T={1,2,3} with weight 
31
31.
𝑆
=
{
1.3
}
→
𝑇
=
{
1
,
3
}
S={1.3}→T={1,3} with weight 
30
30.
𝑆
=
{
1.4
}
→
𝑇
=
{
1
,
3
,
4
}
S={1.4}→T={1,3,4} with weight 
70
70.
𝑆
=
{
2.3
}
→
𝑇
=
{
2
,
3
}
S={2.3}→T={2,3} with weight 
21
21.
𝑆
=
{
2.4
}
→
𝑇
=
{
2
,
3
,
4
}
S={2.4}→T={2,3,4} with weight 
61
61.
𝑆
=
{
3
,
4
}
→
𝑇
=
{
3
,
4
}
S={3,4}→T={3,4} with weight 
60
60.
𝑆
=
{
1
,
2.3
}
→
𝑇
=
{
1
,
2
,
3
}
S={1,2.3}→T={1,2,3} with weight 
31
31.
𝑆
=
{
1
,
2.4
}
→
𝑇
=
{
1
,
2
,
3
,
4
}
S={1,2.4}→T={1,2,3,4} with weight 
71
71.
𝑆
=
{
1
,
3
,
4
}
→
𝑇
=
{
1
,
3
,
4
}
S={1,3,4}→T={1,3,4} with weight 
70
70.
𝑆
=
{
2
,
3
,
4
}
→
𝑇
=
{
2
,
3
,
4
}
S={2,3,4}→T={2,3,4} with weight 
61
61.
𝑆
=
{
1
,
2.3
,
4
}
→
𝑇
=
{
1
,
2
,
3
,
4
}
S={1,2.3,4}→T={1,2,3,4} with weight 
71
71.
Summarizing, the sum of all the node-weighted Steiner trees are:

With size 
1
1 is 
71
71.
With size 
2
2 is 
273
273.
With size 
3
3 is 
233
233.
With size 
4
4 is 
71
71