設 $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