Misalkan $X = (x_1, x_2, \ldots, x_{n-1})$ adalah barisan bilangan bulat sembarang dengan panjang $n - 1$ yang elemen-elemennya berada di antara $1$ dan $n$, inklusif. Tinjuau semua pohon yang memenuhi syarat berikut. Setidaknya satu pohon seperti itu selalu ada. Definisikan $f(X)$ sebagai diameter maksimum di antara pohon-pohon tersebut.

• Pohon tersebut terdiri dari $n$ simpul yang dinomori dari $1$ sampai $n$. Sisi-sisinya dinomori dari $1$ sampai $n - 1$. Untuk setiap $i$ ($1 \le i \le n - 1$), salah satu titik ujung dari sisi $i$ adalah $x_i$.

Di sini, diameter dari sebuah pohon adalah jumlah sisi maksimum pada suatu lintasan antara dua simpul.

Anda diberikan dua barisan bilangan bulat, $A = (a_1, a_2, \ldots, a_{n-1})$ dan $B = (b_1, b_2, \ldots, b_{n-1})$. Setiap elemen di $A$ berada di antara $1$ dan $n$, inklusif. Setiap elemen di $B$ bernilai positif. Anda dapat mengasumsikan bahwa pasangan $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ semuanya berbeda.

Untuk setiap $d = 2, 3, \ldots, n - 1$, selesaikan masalah berikut:

Pilih sebuah barisan bilangan bulat $X = (x_1, x_2, \ldots, x_{n-1})$ yang elemen-elemennya berada di antara $1$ dan $n$, inklusif, dan memenuhi $f(X) = d$. Barisan seperti itu selalu ada. Untuk setiap $i$ ($1 \le i \le n - 1$), Anda membayar biaya sebesar $2^{b_i}$ jika dan hanya jika $x_i \ne a_i$. Carilah total biaya minimum yang mungkin.

Karena setiap jawaban bisa sangat besar, keluarkan hasilnya modulo $998\,244\,353$.

Masukan

Masukan terdiri dari satu kasus uji dengan format berikut.

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

Baris pertama berisi sebuah bilangan bulat $n$ ($3 \le n \le 2 \times 10^5$). Baris kedua berisi $n - 1$ bilangan bulat dalam barisan $A$ ($1 \le a_i \le n$). Baris ketiga berisi $n - 1$ bilangan bulat dalam barisan $B$ ($1 \le b_i \le 10^9$). Dijamin bahwa $(a_i, b_i) \ne (a_j, b_j)$ jika $i \ne j$.

Keluaran

Keluarkan $n - 2$ baris. Baris ke-$k$ harus berisi jawaban untuk $d = k + 1$, yaitu total biaya minimum yang mungkin untuk suatu barisan $X$ sedemikian sehingga $f(X) = k + 1$, modulo $998\,244\,353$.

Contoh

Masukan 1

5
2 4 3 4
1 2 4 8

Keluaran 1

18
2
0

Masukan 2

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

Keluaran 2

454
196
68
36
4
2
0
2

Masukan 3

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

Keluaran 3

0
16777216
150994944
226492415
830472183
671088562
394263947