Description

La route principale de Mazhen est orientée nord-sud, commençant au point le plus au sud et se terminant au point le plus au nord. Le long de cette route, il y a $n - 1$ intersections, divisant l'ensemble de la route en $n$ segments. La $i$-ième intersection du sud au nord relie le $i$-ième segment de la route et le $(i + 1)$-ième segment de la route. En raison d'une ambiguïté potentielle sur la direction, l'intersection et le segment de rang $i$ sont définis comme étant l'intersection et le segment de rang $i$ du sud au nord.

Chaque intersection possède un feu de circulation et, en raison de la nature directionnelle des rues reliées à l'intersection, le temps passé à traverser la même intersection avec la même couleur de feu peut différer selon que l'on va vers le nord ou vers le sud. Le chercheur estime qu'en traversant aléatoirement la $i$-ième intersection du sud au nord, les probabilités de rencontrer un feu rouge, un feu jaune et un feu vert sont respectivement $r_i, y_i, g_i$ ; en traversant la $i$-ième intersection du nord au sud, les probabilités de rencontrer un feu rouge, un feu jaune et un feu vert sont respectivement $r'_i, y'_i, g'_i$. On suppose qu'en arrivant à l'intersection, on rencontrera l'une des trois situations : feu rouge, feu jaune ou feu vert, d'où $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Pour simplifier le problème, le chercheur suppose que, quels que soient la direction et le moment, lorsqu'on rencontre un feu rouge, un feu jaune ou un feu vert, les temps d'attente sont toujours respectivement de $1$ seconde, $2$ secondes et $0$ seconde.

En tant que participant à des compétitions de programmation, le chercheur a rapidement calculé l'espérance du temps nécessaire pour parcourir l'ensemble de la route dans les deux sens, modulo $998\,244\,353$. Cependant, le chercheur souhaite maintenant connaître des informations plus précises. À cette fin, il a mené un test : en partant du début jusqu'à la fin, il a enregistré le temps d'attente total pour atteindre le $i$-ième segment, noté $a_i$ ; puis, en revenant de la fin vers le début, il a enregistré le temps d'attente total pour atteindre le $i$-ième segment, noté $b_i$. Clairement, $a_1 = b_n = 0$ et $a_i \le a_{i+1} \le a_i + 2$ ainsi que $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Soit $c_i = a_i + b_i$. Le chercheur a enregistré tous les $c_i$ ($1 \le i \le n$) lors de ce test.

Le chercheur veut connaître la valeur pratique de ce test ; il espère donc trouver, pour chaque $i = 1, 2, \dots, n$, la probabilité que le « temps d'attente total du point de départ au $i$-ième segment » + le « temps d'attente total du point d'arrivée au $i$-ième segment » soit exactement égal à $c_i$, modulo $998\,244\,353$. Cela le laisse perplexe, c'est pourquoi il vous demande de l'aide.

Entrée

La première ligne de l'entrée contient un seul entier $n$ ($2 \le n \le 2 \times 10^5$).

Les $n - 1$ lignes suivantes contiennent chacune $4$ entiers strictement positifs. Les $4$ entiers strictement positifs de la $i$-ième ligne représentent $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Il est garanti que ces $4(n - 1)$ entiers strictement positifs ne dépassent pas $100$, et que $r_i + y_i$ et $r'_i + y'_i$ sont tous deux $< 1$.

La ligne suivante de l'entrée contient $n$ entiers naturels, où le $i$-ième entier représente $c_i$ ($0 \le c_i \le 2n$). Il est garanti qu'il existe $a_1, a_2, \dots, a_n$ et $b_1, b_2, \dots, b_n$ satisfaisant $a_1 = b_n = 0$ et $a_i \le a_{i+1} \le a_i + 2$ et $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) ainsi que $a_i + b_i = c_i$.

Sortie

Affichez une ligne contenant $n$ entiers naturels. Le $i$-ième entier représente la probabilité que le « temps d'attente total du point de départ au $i$-ième segment » + le « temps d'attente total du point d'arrivée au $i$-ième segment » soit exactement égal à $c_i$, modulo $998\,244\,353$.

Exemple

Exemple 1

2
25 25 25 25
0 1

499122177 748683265

Note

Dans l'exemple, les probabilités de rencontrer un feu rouge/jaune/vert à la $1$-re intersection dans les deux sens sont $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

À ce stade, la probabilité d'atteindre le $1$-er segment du sud au nord avec un temps d'attente $a_1 = 0$ est $1$ (puisqu'aucune intersection n'a été traversée), et la probabilité d'atteindre le $1$-er segment du nord au sud avec un temps d'attente $b_1 = 0$ est $\frac{1}{2}$ (c'est-à-dire avoir un feu vert à la $1$-re intersection), donc la probabilité pour $c_1 = 0$ est $1 \times \frac{1}{2} = \frac{1}{2}$.

De même, les probabilités d'atteindre le $2$-e segment du sud au nord avec des temps d'attente $a_2 = 0, 1$ sont $\frac{1}{2}, \frac{1}{4}$, et les probabilités d'atteindre le $2$-e segment du nord au sud avec des temps d'attente $b_2 = 0, 1$ sont $1, 0$, donc la probabilité pour $c_2 = 1$ est $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.