设 $X = (x_1, x_2, \ldots, x_{n-1})$ 为任意一个长度为 $n - 1$、元素均在 $1$ 到 $n$ 之间（含两端）的整数序列。考虑所有满足如下条件的树。这样的树总是至少存在一棵。定义 $f(X)$ 为这些树中的最大直径。

• 该树包含 $n$ 个节点，编号为 $1$ 到 $n$。边编号为 $1$ 到 $n - 1$。对于每个 $i$（$1 \le i \le n - 1$），边 $i$ 的其中一个端点是 $x_i$。

这里，一棵树的直径是指两个节点之间路径上的最大边数。

给定两个整数序列 $A = (a_1, a_2, \ldots, a_{n-1})$ 和 $B = (b_1, b_2, \ldots, b_{n-1})$。$A$ 中的每个元素均在 $1$ 到 $n$ 之间（含两端）。$B$ 中的每个元素均为正整数。你可以假设二元组 $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ 互不相同。

对于每个 $d = 2, 3, \ldots, n - 1$，解决以下问题：

选择一个元素均在 $1$ 到 $n$ 之间（含两端）且满足 $f(X) = d$ 的整数序列 $X = (x_1, x_2, \ldots, x_{n-1})$。这样的序列总是存在。对于每个 $i$（$1 \le i \le n - 1$），当且仅当 $x_i \ne a_i$ 时，你需要支付 $2^{b_i}$ 的代价。求最小可能的总代价。

由于每个答案可能很大，请将其对 $998\,244\,353$ 取模后输出。

输入格式

输入包含单个测试用例，格式如下。

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

第一行包含一个整数 $n$（$3 \le n \le 2 \times 10^5$）。第二行包含序列 $A$ 中的 $n - 1$ 个整数（$1 \le a_i \le n$）。第三行包含序列 $B$ 中的 $n - 1$ 个整数（$1 \le b_i \le 10^9$）。保证当 $i \ne j$ 时有 $(a_i, b_i) \ne (a_j, b_j)$。

输出格式

输出 $n - 2$ 行。第 $k$ 行应包含 $d = k + 1$ 时的答案，即满足 $f(X) = k + 1$ 的序列 $X$ 的最小可能总代价对 $998\,244\,353$ 取模的结果。

样例

输入格式 1

5
2 4 3 4
1 2 4 8

输出格式 1

18
2
0

输入格式 2

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

输出格式 2

454
196
68
36
4
2
0
2

输入格式 3

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

输出格式 3

0
16777216
150994944
226492415
830472183
671088562
394263947