Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a rooted tree with $N$ nodes (numbered $1$ through $N$); node $1$ is the root. For each valid $i$, the $i$-th node has a value $v_{i}$ and another parameter $m_{i}$.

A leaf is a node without sons. Let's denote the number of leaf nodes in the tree by $L$ and their numbers by $l_{1}, l_{2}, \ldots, l_{L}$, in increasing order. Then, for each valid $i$, let's define the answer for the leaf $l_{i}$ in the following way:
Consider the path from the root to $l_{i}$. For each node on this path (including the root and this leaf), choose a non-negative integer and multiply the value of this node by it.
Sum up the resulting values of all nodes on this path.
The answer $a_{i}$ for this leaf is defined as the maximum possible remainder of this sum modulo $m_{l_{i}}$.

Find the answers for all leaves.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the following $N-1$ lines contains two space-separated integers $x$ and $y$ denoting that nodes $x$ and $y$ are connected by an edge.
The next line contains $N$ space-separated integers $v_{1}, v_{2}, \ldots, v_{N}$.
The last line contains $N$ space-separated integers $m_{1}, m_{2}, \ldots, m_{N}$.

------ Output ------
For each test case, print a single line containing $L$ space-separated integers $a_{1}, a_{2}, \ldots, a_{L}$.

------ Constraints ------
$1 ≤ T ≤ 8$
$2 ≤ N ≤ 10^{5}$
$1 ≤ x, y ≤ N$
$1 ≤ v_{i} ≤ 10^{18}$ for each valid $i$
$1 ≤ m_{i} ≤ 10^{18}$ for each valid $i$
the graph described on the input is a tree

------ Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------
1
5
1 2
2 5
1 3
3 4
2 3 4 6 7
1 2 3 2 10
----- Sample Output 1 ------
0 9
----- explanation 1 ------
Example case 1: There are only two leaves, $l_{1} = 4$ and $l_{2} = 5$. The answers for them are $a_{1} = 0$ and $a_{2} = 9$.

见题面

见题面