Gọi $X = (x_1, x_2, \ldots, x_{n-1})$ là một dãy số nguyên bất kỳ có độ dài $n - 1$ với các phần tử nằm trong đoạn từ $1$ đến $n$ (bao gồm cả hai đầu mút). Xét tất cả các cây thỏa mãn điều kiện sau. Luôn tồn tại ít nhất một cây như vậy. Định nghĩa $f(X)$ là đường kính lớn nhất trong số các cây này.

• Cây gồm $n$ đỉnh được đánh số từ $1$ đến $n$. Các cạnh được đánh số từ $1$ đến $n - 1$. Với mỗi $i$ ($1 \le i \le n - 1$), một trong hai đầu mút của cạnh $i$ là $x_i$.

Ở đây, đường kính của một cây là số cạnh lớn nhất trên một đường đi giữa hai đỉnh.

Bạn được cho hai dãy số nguyên $A = (a_1, a_2, \ldots, a_{n-1})$ và $B = (b_1, b_2, \ldots, b_{n-1})$. Mỗi phần tử trong $A$ nằm trong đoạn từ $1$ đến $n$ (bao gồm cả hai đầu mút). Mỗi phần tử trong $B$ là số nguyên dương. Bạn có thể giả sử rằng các cặp $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ là đôi một phân biệt.

Với mỗi $d = 2, 3, \ldots, n - 1$, hãy giải bài toán sau:

Chọn một dãy số nguyên $X = (x_1, x_2, \ldots, x_{n-1})$ có các phần tử nằm trong đoạn từ $1$ đến $n$ (bao gồm cả hai đầu mút) và thỏa mãn $f(X) = d$. Một dãy như vậy luôn tồn tại. Với mỗi $i$ ($1 \le i \le n - 1$), bạn phải trả chi phí là $2^{b_i}$ khi và chỉ khi $x_i \ne a_i$. Hãy tìm tổng chi phí nhỏ nhất có thể.

Vì mỗi câu trả lời có thể rất lớn, hãy in ra kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dữ liệu vào gồm một bộ kiểm tra duy nhất có định dạng như sau.

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

Dòng đầu tiên chứa một số nguyên $n$ ($3 \le n \le 2 \times 10^5$). Dòng thứ hai chứa $n - 1$ số nguyên của dãy $A$ ($1 \le a_i \le n$). Dòng thứ ba chứa $n - 1$ số nguyên của dãy $B$ ($1 \le b_i \le 10^9$). Dữ liệu đảm bảo rằng $(a_i, b_i) \ne (a_j, b_j)$ nếu $i \ne j$.

Dữ liệu ra

In ra $n - 2$ dòng. Dòng thứ $k$ chứa câu trả lời cho $d = k + 1$, tức là tổng chi phí nhỏ nhất có thể cho một dãy $X$ sao cho $f(X) = k + 1$, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

5
2 4 3 4
1 2 4 8

Dữ liệu ra 1

18
2
0

Dữ liệu vào 2

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

Dữ liệu ra 2

454
196
68
36
4
2
0
2

Dữ liệu vào 3

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

Dữ liệu ra 3

0
16777216
150994944
226492415
830472183
671088562
394263947