Descripción

La carretera principal de Mazhen está orientada de norte a sur, comenzando en el punto más al sur y terminando en el punto más al norte. A lo largo de esta carretera hay $n - 1$ intersecciones, que dividen toda la carretera en $n$ segmentos. La $i$-ésima intersección de sur a norte conecta el $i$-ésimo segmento de la carretera y el $(i + 1)$-ésimo segmento de la carretera. Debido a la posible ambigüedad en la dirección, la intersección y el segmento $i$-ésimos se definen como la intersección y el segmento $i$-ésimos de sur a norte.

Cada intersección tiene un semáforo y, debido a la naturaleza direccional de las calles conectadas a la intersección, el tiempo empleado en cruzar la misma intersección con el mismo color de luz puede diferir al ir hacia el norte o hacia el sur. El investigador cree que al pasar aleatoriamente por la $i$-ésima intersección de sur a norte, las probabilidades de encontrar luz roja, luz amarilla y luz verde son $r_i, y_i, g_i$, respectivamente; al pasar por la $i$-ésima intersección de norte a sur, las probabilidades de encontrar luz roja, luz amarilla y luz verde son $r'_i, y'_i, g'_i$, respectivamente. Se asume que al llegar a la intersección se encontrará una de las tres situaciones: luz roja, luz amarilla o luz verde, por lo que $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Para simplificar el problema, el investigador asume que independientemente de la dirección y el momento, al encontrar una luz roja, amarilla o verde, los tiempos de espera son siempre $1$ segundo, $2$ segundos y $0$ segundos, respectivamente.

Como participante de programación competitiva, el investigador calculó rápidamente el tiempo esperado para recorrer todo el tramo de carretera en ambas direcciones, módulo $998\,244\,353$. Sin embargo, ahora el investigador quiere conocer información más específica. Con este fin, realizó una prueba: partiendo desde el inicio hasta el final, registró el tiempo total de espera para llegar al $i$-ésimo segmento, denotado como $a_i$; luego, regresando desde el final hasta el inicio, registró el tiempo total de espera para llegar al $i$-ésimo segmento, denotado como $b_i$. Claramente, $a_1 = b_n = 0$ y $a_i \le a_{i+1} \le a_i + 2$ y $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Sea $c_i = a_i + b_i$. El investigador registró todos los $c_i$ ($1 \le i \le n$) de esta prueba.

El investigador quiere conocer el valor práctico de esta prueba, por lo que espera hallar la probabilidad para cada $i = 1, 2, \dots, n$ de que el «tiempo total de espera desde el punto de partida hasta el $i$-ésimo segmento» + «tiempo total de espera desde el punto final hasta el $i$-ésimo segmento» sea exactamente igual a $c_i$, módulo $998\,244\,353$. Esto lo tiene perplejo, así que acude a ti en busca de ayuda.

Entrada

La primera línea de la entrada contiene un solo entero $n$ ($2 \le n \le 2 \times 10^5$).

Las siguientes $n - 1$ líneas contienen cada una $4$ enteros positivos. Los $4$ enteros positivos de la $i$-ésima línea representan $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Se garantiza que estos $4(n - 1)$ enteros positivos no superan $100$, y que tanto $r_i + y_i$ como $r'_i + y'_i$ son $< 1$.

La siguiente línea de la entrada contiene $n$ enteros no negativos, donde el $i$-ésimo entero representa $c_i$ ($0 \le c_i \le 2n$). Se garantiza que existen $a_1, a_2, \dots, a_n$ y $b_1, b_2, \dots, b_n$ que satisfacen $a_1 = b_n = 0$ y $a_i \le a_{i+1} \le a_i + 2$ y $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) y $a_i + b_i = c_i$.

Salida

Imprime una línea con $n$ enteros no negativos. El $i$-ésimo entero representa la probabilidad de que el «tiempo total de espera desde el punto de partida hasta el $i$-ésimo segmento» + «tiempo total de espera desde el punto final hasta el $i$-ésimo segmento» sea exactamente igual a $c_i$, módulo $998\,244\,353$.

Ejemplo

Ejemplo 1

2
25 25 25 25
0 1

499122177 748683265

Nota

En el ejemplo, las probabilidades de encontrar luces roja/amarilla/verde en la $1$-ra intersección en ambas direcciones son $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

En este punto, la probabilidad de llegar al $1$-er segmento de sur a norte con tiempo de espera $a_1 = 0$ es $1$ (ya que no se cruzó ninguna intersección), y la probabilidad de llegar al $1$-er segmento de norte a sur con tiempo de espera $b_1 = 0$ es $\frac{1}{2}$ (es decir, encontrar luz verde en la $1$-ra intersección), por lo que la probabilidad para $c_1 = 0$ es $1 \times \frac{1}{2} = \frac{1}{2}$.

De manera similar, las probabilidades de llegar al $2$-do segmento de sur a norte con tiempos de espera $a_2 = 0, 1$ son $\frac{1}{2}, \frac{1}{4}$, y las probabilidades de llegar al $2$-do segmento de norte a sur con tiempos de espera $b_2 = 0, 1$ son $1, 0$, por lo que la probabilidad para $c_2 = 1$ es $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.