Låt $X = (x_1, x_2, \ldots, x_{n-1})$ vara en godtycklig heltalsföljd av längd $n - 1$ vars element ligger mellan $1$ och $n$, inklusive. Betrakta alla träd som uppfyller följande villkor. Det finns alltid minst ett sådant träd. Definiera $f(X)$ som den maximala diametern bland dessa träd.

• Trädet består av $n$ noder numrerade från $1$ till $n$. Kanterna är numrerade från $1$ till $n - 1$. För varje $i$ ($1 \le i \le n - 1$) är en av ändpunkterna för kant $i$ lika med $x_i$.

Här är diametern av ett träd det maximala antalet kanter på en väg mellan två noder.

Du får två heltalsföljder, $A = (a_1, a_2, \ldots, a_{n-1})$ och $B = (b_1, b_2, \ldots, b_{n-1})$. Varje element i $A$ ligger mellan $1$ och $n$, inklusive. Varje element i $B$ är positivt. Du kan anta att paren $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ är parvis olika.

För varje $d = 2, 3, \ldots, n - 1$, lös följande problem:

Välj en heltalsföljd $X = (x_1, x_2, \ldots, x_{n-1})$ vars element ligger mellan $1$ och $n$, inklusive, och som uppfyller $f(X) = d$. En sådan följd existerar alltid. För varje $i$ ($1 \le i \le n - 1$) betalar du en kostnad på $2^{b_i}$ om och endast om $x_i \ne a_i$. Hitta den minsta möjliga totalkostnaden.

Eftersom varje svar kan vara stort, skriv ut det modulo $998\,244\,353$.

Indata

Indata består av ett enda testfall i följande format.

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

Den första raden innehåller ett heltal $n$ ($3 \le n \le 2 \times 10^5$). Den andra raden innehåller $n - 1$ heltal i följden $A$ ($1 \le a_i \le n$). Den tredje raden innehåller $n - 1$ heltal i följden $B$ ($1 \le b_i \le 10^9$). Det garanteras att $(a_i, b_i) \ne (a_j, b_j)$ om $i \ne j$.

Utdata

Skriv ut $n - 2$ rader. Den $k$-te raden ska innehålla svaret för $d = k + 1$, det vill säga den minsta möjliga totalkostnaden för en följd $X$ sådan att $f(X) = k + 1$, modulo $998\,244\,353$.

Exempel

Indata 1

5
2 4 3 4
1 2 4 8

Utdata 1

18
2
0

Indata 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

Indata 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