B. AUBREY
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
SPROUT MOLES are highly intelligent creatures, but become dangerously vicious when they are lost
— Aubrey, Prologue

School is starting, and Aubrey is excited for the activities she is going to perform at school. During the break, Aubrey enjoys her favorite hobby of hunting sprout moles.

The school yard has a tree containing $$$n$$$ nodes rooted at some node (let that node be $$$r$$$). The $$$i$$$-th $$$(1 \le i \le n)$$$ node has $$$a_i$$$ sprout moles. Aubrey starts her hunt by choosing a node $$$i$$$, and then chooses a subset of nodes in the subtree of node $$$i$$$, and starts hunting the sprout moles in each node in the chosen subset.

When Aubrey hunts a group of $$$a_i$$$ sprout moles in a single node $$$i$$$, her hunting score gets XORed by $$$a_i$$$, and Aubrey initially has a hunting score of $$$0$$$.

Now consider the set of all possible distinct final scores Aubrey can achieve by choosing a subset of nodes from the subtree of node $$$i$$$, name it $$$S_i$$$. $$$f(i)$$$ is equal to the summation of the elements of $$$S_i$$$.

Now Aubrey does not know where the tree is rooted at, so she wants to know, from every root $$$r$$$ from $$$1$$$ to $$$n$$$ inclusive, what is the summation of $$$f(i)$$$ over all nodes $$$i$$$ $$$(1 \le i \le n)$$$ assuming the tree is rooted at $$$r$$$? Since $$$\displaystyle\sum_{i=1}^n f(i)$$$ can be very large, Aubrey wants to find its value modulo $$$998244353$$$.

Input

The first line of input contains one integer $$$n$$$ $$$(1 \le n \le 2\times 10^5)$$$ — the number of nodes in the tree.

The next $$$n-1$$$ lines each contain $$$2$$$ integers $$$u_i, v_i$$$ $$$(1 \le u_i, v_i \le n)$$$ separated by a space — the edges of the tree.

The next line contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ $$$(0 \le a_i \lt 2^{30})$$$ separated by spaces — the number of sprout moles in each node.

Output

Output one line containing $$$n$$$ integers. The $$$r$$$-th $$$(1 \le r \le n)$$$ of them contains $$$\displaystyle\sum_{i=1}^n f(i)$$$ modulo $$$998244353$$$ when the tree is rooted at node $$$r$$$.

Examples
Input
3
1 2
1 3
1 2 3
Output
11 15 14
Input
3
1 2
1 3
1 1 1
Output
3 3 3
Note

In the first sample, there are three possible roots :

  1. The tree is rooted at $$$1$$$. In that case, there are $$$3$$$ possible subtrees : $$$\{\{1,2,3\}, \{2\}, \{3\}\}$$$. The sets of all possible XOR sums over all subsets in each subtree are $$$\{\{0,1,2,3\}, \{0,2\}, \{0,3\}\}$$$. Their summation is $$$0 + 1 + 2 + 3 + 0 + 2 + 0 + 3 = 11$$$.
  2. The tree is rooted at $$$2$$$. In that case, there are $$$3$$$ possible subtrees : $$$\{\{1,2,3\}, \{1,3\}, \{3\}\}$$$. The sets of all possible XOR sums over all subsets in each subtree are $$$\{\{0,1,2,3\}, \{0,1,2,3\}, \{0,3\}\}$$$. Their summation is $$$0 + 1 + 2 + 3 + 0 + 1 + 2 + 3 + 0 + 3 = 15$$$.
  3. The tree is rooted at $$$3$$$. In that case, there are $$$3$$$ possible subtrees : $$$\{\{1,2,3\}, \{1,2\}, \{2\}\}$$$. The sets of all possible XOR sums over all subsets in each subtree are $$$\{\{0,1,2,3\}, \{0,1,2,3\}, \{0,2\}\}$$$. Their summation is $$$0 + 1 + 2 + 3 + 0 + 1 + 2 + 3 + 0 + 2 = 14$$$.
Aubrey being excited to start her sprout mole hunt