$X = (x_1, x_2, \ldots, x_{n-1})$ を、各要素が $1$ 以上 $n$ 以下の整数である長さ $n - 1$ の任意の整数列とします。次の条件を満たす木すべてを考えます。このような木は常に少なくとも一つ存在します。これらの木の中での直径の最大値を $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} $$

1 行目には整数 $n$（$3 \le n \le 2 \times 10^5$）が与えられます。2 行目には数列 $A$ の $n - 1$ 個の整数（$1 \le a_i \le n$）が与えられます。3 行目には数列 $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