Soit $X = (x_1, x_2, \ldots, x_{n-1})$ une suite quelconque d'entiers de longueur $n - 1$ dont les éléments sont compris entre $1$ et $n$ inclus. Considérons tous les arbres satisfaisant la condition suivante. Il existe toujours au moins un tel arbre. On définit $f(X)$ comme le diamètre maximum parmi ces arbres.

• L'arbre est constitué de $n$ nœuds numérotés de $1$ à $n$. Les arêtes sont numérotées de $1$ à $n - 1$. Pour chaque $i$ ($1 \le i \le n - 1$), l'une des extrémités de l'arête $i$ est $x_i$.

Ici, le diamètre d'un arbre est le nombre maximum d'arêtes sur un chemin entre deux nœuds.

On vous donne deux suites d'entiers, $A = (a_1, a_2, \ldots, a_{n-1})$ et $B = (b_1, b_2, \ldots, b_{n-1})$. Chaque élément de $A$ est compris entre $1$ et $n$ inclus. Chaque élément de $B$ est strictement positif. Vous pouvez supposer que les paires $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ sont deux à deux distinctes.

Pour chaque $d = 2, 3, \ldots, n - 1$, résolvez le problème suivant :

Choisissez une suite d'entiers $X = (x_1, x_2, \ldots, x_{n-1})$ dont les éléments sont compris entre $1$ et $n$ inclus, et qui satisfait $f(X) = d$. Une telle suite existe toujours. Pour chaque $i$ ($1 \le i \le n - 1$), vous payez un coût de $2^{b_i}$ si et seulement si $x_i \ne a_i$. Trouvez le coût total minimum possible.

Comme chaque réponse peut être grande, affichez-la modulo $998\,244\,353$.

Entrée

L'entrée consiste en un seul cas de test au format suivant.

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

La première ligne contient un entier $n$ ($3 \le n \le 2 \times 10^5$). La deuxième ligne contient $n - 1$ entiers de la suite $A$ ($1 \le a_i \le n$). La troisième ligne contient $n - 1$ entiers de la suite $B$ ($1 \le b_i \le 10^9$). Il est garanti que $(a_i, b_i) \ne (a_j, b_j)$ si $i \ne j$.

Sortie

Affichez $n - 2$ lignes. La $k$-ième ligne doit contenir la réponse pour $d = k + 1$, c'est-à-dire le coût total minimum possible pour une suite $X$ telle que $f(X) = k + 1$, modulo $998\,244\,353$.

Exemples

Entrée 1

5
2 4 3 4
1 2 4 8

Sortie 1

18
2
0

Entrée 2

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

Sortie 2

454
196
68
36
4
2
0
2

Entrée 3

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

Sortie 3

0
16777216
150994944
226492415
830472183
671088562
394263947