K. Finding The Way Home
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Every time Da7doo7 gets fired he goes to a new tree and gets lost.

Da7doo7 is currently lost in the tree and needs to find his way back home, which is located at node $$$1$$$ the root. Each node in the tree has a corresponding value, denoted by $$$b_i$$$. There is also an array of length $$$n$$$ that represents the fun of the $$$i$$$-th day $$$a_i$$$.

Every day, Da7doo7 will go to an adjacent node on the path leading to the root. As he reaches a new node, his excitement level increases by adding the product of the node value of the current node $$$b_{\texttt{current node}}$$$ with the corresponding fun value of the current day $$$a_{\texttt{current day}}$$$.

For each possible starting node in the tree, your task is to calculate the total excitement that Da7doo7 can achieve by following the path to the root.

The above picture illustrates the example.

In summary, you need to determine the total excitement Da7doo7 can experience by selecting different starting nodes and following the path to the root modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T\le 1000)$$$ denoting the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1\le n\le 3\cdot 10^5)$$$ indicating the number of nodes of the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ $$$(1\le a_i\le 10^9)$$$ — the fun of each day.

The third line of each test case contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$ $$$(1\le b_i\le 10^9)$$$ — the value of each node.

Each of the following $$$n-1$$$ lines of each test case contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) — the vertices connected by an edge. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

Output

For each test case, print $$$n$$$ lines, the $$$i$$$-th of which contains the answer which represents the total excitement Da7doo7 can experience if he started from node $$$i$$$ modulo $$$998\,244\,353$$$.

Example
Input
1
13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2
2 3
3 4
4 5
1 6
1 7
3 8
8 9
6 10
10 11
11 12
7 13
Output
1
4
10
20
35
8
9
24
47
25
53
93
30
Note

Considering the answer for starting position $$$11$$$: the path to the root is $$$11 \rightarrow 10 \rightarrow 6 \rightarrow 1$$$.

So the total excitement that Da7doo7 can achieve is: $$$b_{11}\cdot a_1 + b_{10}\cdot a_2 + b_6\cdot a_3 + b_1\cdot a_4 = 11\cdot 1 + 10\cdot 2 + 6\cdot 3 + 1\cdot 4 = 53$$$.