Let $X = (x_1, x_2, \ldots, x_{n-1})$ be any integer sequence of length $n - 1$ whose elements are between $1$ and $n$, inclusive. Consider all trees satisfying the following condition. At least one such tree always exists. Define $f(X)$ as the maximum diameter among these trees.

• The tree consists of $n$ nodes numbered $1$ through $n$. Edges are numbered $1$ through $n - 1$. For each $i$ ($1 \le i \le n - 1$), one of the endpoints of edge $i$ is $x_i$.

Here, the diameter of a tree is the maximum number of edges on a path between two nodes.

You are given two integer sequences, $A = (a_1, a_2, \ldots, a_{n-1})$ and $B = (b_1, b_2, \ldots, b_{n-1})$. Each element in $A$ is between $1$ and $n$, inclusive. Each element in $B$ is positive. You can assume that the pairs $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ are distinct.

For each $d = 2, 3, \ldots, n - 1$, solve the following problem:

Choose an integer sequence $X = (x_1, x_2, \ldots, x_{n-1})$ whose elements are between $1$ and $n$, inclusive, and that satisfies $f(X) = d$. Such a sequence always exists. For each $i$ ($1 \le i \le n - 1$), you pay a cost of $2^{b_i}$ if and only if $x_i \ne a_i$. Find the minimum possible total cost.

Because each answer may be large, output it modulo $998\,244\,353$.

Input

The input consists of a single test case of the following format.

$$ \begin{aligned} &n \\ &a_1 \ a_2 \ \cdots \ a_{n-1} \\ &b_1 \ b_2 \ \cdots \ b_{n-1} \end{aligned} $$

The first line contains an integer $n$ ($3 \le n \le 2 \times 10^5$). The second line contains $n - 1$ integers in the sequence $A$ ($1 \le a_i \le n$). The third line contains $n - 1$ integers in the sequence $B$ ($1 \le b_i \le 10^9$). It is guaranteed that $(a_i, b_i) \ne (a_j, b_j)$ if $i \ne j$.

Output

Output $n - 2$ lines. The $k$-th line should contain the answer for $d = k + 1$, i.e., the minimal possible total cost for a sequence $X$ such that $f(X) = k + 1$, modulo $998\,244\,353$.

Examples

Input 1

5
2 4 3 4
1 2 4 8

Output 1

18
2
0

Input 2

10
6 2 1 6 10 4 6 10 4
1 1 7 8 1 5 5 5 10

Output 2

454
196
68
36
4
2
0
2

Input 3

9
1 1 1 1 1 1 1 1
24 27 30 33 36 39 42 45

Output 3

0
16777216
150994944
226492415
830472183
671088562
394263947