Látum $X = (x_1, x_2, \ldots, x_{n-1})$ vera hvaða heiltalnastrump sem er af lengd $n - 1$ þar sem stök hans eru á milli $1$ og $n$, báðir endar meðtaldir. Skoðum öll tré sem uppfylla eftirfarandi skilyrði. Að minnsta kosti eitt slíkt tré er alltaf til. Skilgreinum $f(X)$ sem hámarksþvermál meðal þessara trjáa.

• Tréð samanstendur af $n$ hnútum sem eru númeraðir frá $1$ til $n$. Leggirnir eru númeraðir frá $1$ til $n - 1$. Fyrir hvert $i$ ($1 \le i \le n - 1$) er annar endapunktur leggs $i$ jafn $x_i$.

Hér er þvermál trés mesta mögulega fjöldi leggja á einföldum vegi milli tveggja hnúta.

Gefnar eru tvær heiltalnarunur, $A = (a_1, a_2, \ldots, a_{n-1})$ og $B = (b_1, b_2, \ldots, b_{n-1})$. Hvert stak í $A$ er á milli $1$ og $n$, báðir endar meðtaldir. Hvert stak í $B$ er jákvætt. Þú getur gert ráð fyrir að pörin $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ séu öll ólík.

Fyrir hvert $d = 2, 3, \ldots, n - 1$, leystu eftirfarandi verkefni:

Veldu heiltalnarunu $X = (x_1, x_2, \ldots, x_{n-1})$ þar sem stökin eru á milli $1$ og $n$, báðir endar meðtaldir, og uppfyllir $f(X) = d$. Slík runa er alltaf til. Fyrir hvert $i$ ($1 \le i \le n - 1$) borgar þú kostnað upp á $2^{b_i}$ ef og aðeins ef $x_i \ne a_i$. Finndu minnsta mögulega heildarkostnað.

Þar sem hvert svar getur verið stórt skal prenta það modulo $998\,244\,353$.

Inntak

Inntakið samanstendur af einu prófunartilfelli á eftirfarandi sniði.

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

Fyrsta línan inniheldur heiltölu $n$ ($3 \le n \le 2 \times 10^5$). Önnur línan inniheldur $n - 1$ heiltölur í rununni $A$ ($1 \le a_i \le n$). Þriðja línan inniheldur $n - 1$ heiltölur í rununni $B$ ($1 \le b_i \le 10^9$). Það er tryggt að $(a_i, b_i) \ne (a_j, b_j)$ ef $i \ne j$.

Úttak

Prentið $n - 2$ línur. $k$-ta línan á að innihalda svarið fyrir $d = k + 1$, þ.e. minnsta mögulega heildarkostnað fyrir runu $X$ þannig að $f(X) = k + 1$, modulo $998\,244\,353$.

Dæmi

Inntak 1

5
2 4 3 4
1 2 4 8

Úttak 1

18
2
0

Inntak 2

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

Úttak 2

454
196
68
36
4
2
0
2

Inntak 3

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

Úttak 3

0
16777216
150994944
226492415
830472183
671088562
394263947