Sei $X = (x_1, x_2, \ldots, x_{n-1})$ eine beliebige Folge ganzer Zahlen der Länge $n - 1$, deren Elemente zwischen $1$ und $n$ (einschließlich) liegen. Betrachte alle Bäume, die die folgende Bedingung erfüllen. Mindestens ein solcher Baum existiert immer. Definiere $f(X)$ als den maximalen Durchmesser unter diesen Bäumen.

• Der Baum besteht aus $n$ Knoten, die von $1$ bis $n$ nummeriert sind. Die Kanten sind von $1$ bis $n - 1$ nummeriert. Für jedes $i$ ($1 \le i \le n - 1$) ist einer der Endpunkte der Kante $i$ gleich $x_i$.

Hierbei ist der Durchmesser eines Baumes die maximale Anzahl von Kanten auf einem Pfad zwischen zwei Knoten.

Gegeben sind zwei Folgen ganzer Zahlen, $A = (a_1, a_2, \ldots, a_{n-1})$ und $B = (b_1, b_2, \ldots, b_{n-1})$. Jedes Element in $A$ liegt zwischen $1$ und $n$ (einschließlich). Jedes Element in $B$ ist positiv. Du kannst davon ausgehen, dass die Paare $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ paarweise verschieden sind.

Löse für jedes $d = 2, 3, \ldots, n - 1$ das folgende Problem:

Wähle eine Folge ganzer Zahlen $X = (x_1, x_2, \ldots, x_{n-1})$, deren Elemente zwischen $1$ und $n$ (einschließlich) liegen und die $f(X) = d$ erfüllt. Eine solche Folge existiert immer. Für jedes $i$ ($1 \le i \le n - 1$) zahlst du Kosten in Höhe von $2^{b_i}$ genau dann, wenn $x_i \ne a_i$ gilt. Finde die minimal möglichen Gesamtkosten.

Da jede Antwort groß sein kann, gib sie modulo $998\,244\,353$ aus.

Eingabe

Die Eingabe besteht aus einem einzelnen Testfall im folgenden Format.

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

Die erste Zeile enthält eine ganze Zahl $n$ ($3 \le n \le 2 \times 10^5$). Die zweite Zeile enthält $n - 1$ ganze Zahlen der Folge $A$ ($1 \le a_i \le n$). Die dritte Zeile enthält $n - 1$ ganze Zahlen der Folge $B$ ($1 \le b_i \le 10^9$). Es wird garantiert, dass $(a_i, b_i) \ne (a_j, b_j)$ gilt, falls $i \ne j$.

Ausgabe

Gib $n - 2$ Zeilen aus. Die $k$-te Zeile soll die Antwort für $d = k + 1$ enthalten, d. h. die minimal möglichen Gesamtkosten für eine Folge $X$ mit $f(X) = k + 1$, modulo $998\,244\,353$.

Beispiele

Eingabe 1

5
2 4 3 4
1 2 4 8

Ausgabe 1

18
2
0

Eingabe 2

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

Ausgabe 2

454
196
68
36
4
2
0
2

Eingabe 3

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

Ausgabe 3

0
16777216
150994944
226492415
830472183
671088562
394263947