Sea $X = (x_1, x_2, \ldots, x_{n-1})$ cualquier secuencia de enteros de longitud $n - 1$ cuyos elementos están entre $1$ y $n$, inclusive. Considera todos los árboles que satisfacen la siguiente condición. Siempre existe al menos un árbol así. Define $f(X)$ como el diámetro máximo entre estos árboles.

• El árbol consta de $n$ nodos numerados del $1$ al $n$. Las aristas están numeradas del $1$ al $n - 1$. Para cada $i$ ($1 \le i \le n - 1$), uno de los extremos de la arista $i$ es $x_i$.

Aquí, el diámetro de un árbol es el número máximo de aristas en un camino entre dos nodos.

Se te dan dos secuencias de enteros, $A = (a_1, a_2, \ldots, a_{n-1})$ y $B = (b_1, b_2, \ldots, b_{n-1})$. Cada elemento de $A$ está entre $1$ y $n$, inclusive. Cada elemento de $B$ es positivo. Puedes suponer que los pares $(a_1, b_1), (a_2, b_2), \ldots, (a_{n-1}, b_{n-1})$ son distintos.

Para cada $d = 2, 3, \ldots, n - 1$, resuelve el siguiente problema:

Elige una secuencia de enteros $X = (x_1, x_2, \ldots, x_{n-1})$ cuyos elementos estén entre $1$ y $n$, inclusive, y que satisfaga $f(X) = d$. Dicha secuencia siempre existe. Para cada $i$ ($1 \le i \le n - 1$), pagas un costo de $2^{b_i}$ si y solo si $x_i \ne a_i$. Encuentra el costo total mínimo posible.

Como cada respuesta puede ser grande, imprímela módulo $998\,244\,353$.

Entrada

La entrada consta de un único caso de prueba con el siguiente formato.

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

La primera línea contiene un entero $n$ ($3 \le n \le 2 \times 10^5$). La segunda línea contiene $n - 1$ enteros de la secuencia $A$ ($1 \le a_i \le n$). La tercera línea contiene $n - 1$ enteros de la secuencia $B$ ($1 \le b_i \le 10^9$). Se garantiza que $(a_i, b_i) \ne (a_j, b_j)$ si $i \ne j$.

Salida

Imprime $n - 2$ líneas. La $k$-ésima línea debe contener la respuesta para $d = k + 1$, es decir, el costo total mínimo posible para una secuencia $X$ tal que $f(X) = k + 1$, módulo $998\,244\,353$.

Ejemplos

Entrada 1

5
2 4 3 4
1 2 4 8

Salida 1

18
2
0

Entrada 2

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

Salida 2

454
196
68
36
4
2
0
2

Entrada 3

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

Salida 3

0
16777216
150994944
226492415
830472183
671088562
394263947