La $X = (x_1, x_2, \ldots, x_{n-1})$ være en vilkårlig heltallsfølge med lengde $n - 1$ der elementene er mellom $1$ og $n$, inkludert. Betrakt alle trær som oppfyller følgende betingelse. Det finnes alltid minst ett slikt tre. Definer $f(X)$ som den maksimale diameteren blant disse trærne.

• Treet består av $n$ noder nummerert fra $1$ til $n$. Kantene er nummerert fra $1$ til $n - 1$. For hver $i$ ($1 \le i \le n - 1$) er ett av endepunktene til kant $i$ lik $x_i$.

Her er diameteren til et tre det maksimale antallet kanter på en sti mellom to noder.

Du får gitt to heltallsfølger, $A = (a_1, a_2, \ldots, a_{n-1})$ og $B = (b_1, b_2, \ldots, b_{n-1})$. Hvert element i $A$ er mellom $1$ og $n$, inkludert. Hvert element i $B$ er positivt. Du kan anta at parene $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ er parvis forskjellige.

For hver $d = 2, 3, \ldots, n - 1$, løs følgende problem:

Velg en heltallsfølge $X = (x_1, x_2, \ldots, x_{n-1})$ der elementene er mellom $1$ og $n$, inkludert, og som oppfyller $f(X) = d$. En slik følge eksisterer alltid. For hver $i$ ($1 \le i \le n - 1$) betaler du en kostnad på $2^{b_i}$ hvis og bare hvis $x_i \ne a_i$. Finn den minste mulige totalkostnaden.

Fordi hvert svar kan være stort, skriv det ut modulo $998\,244\,353$.

Inndata

Inndataene består av ett enkelt testtilfelle på følgende format.

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

Den første linjen inneholder et heltall $n$ ($3 \le n \le 2 \times 10^5$). Den andre linjen inneholder $n - 1$ heltall i følgen $A$ ($1 \le a_i \le n$). Den tredje linjen inneholder $n - 1$ heltall i følgen $B$ ($1 \le b_i \le 10^9$). Det er garantert at $(a_i, b_i) \ne (a_j, b_j)$ hvis $i \ne j$.

Utdata

Skriv ut $n - 2$ linjer. Den $k$-te linjen skal inneholde svaret for $d = k + 1$, det vil si den minste mulige totalkostnaden for en følge $X$ slik at $f(X) = k + 1$, modulo $998\,244\,353$.

Eksempler

Inndata 1

5
2 4 3 4
1 2 4 8

Utdata 1

18
2
0

Inndata 2

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

Utdata 2

454
196
68
36
4
2
0
2

Inndata 3

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

Utdata 3

0
16777216
150994944
226492415
830472183
671088562
394263947