Beschreibung

Die Hauptstraße von Mazhen verläuft in Nord-Süd-Richtung, beginnend am südlichsten Punkt und endend am nördlichsten Punkt. Entlang dieser Straße gibt es $n - 1$ Kreuzungen, die die gesamte Straße in $n$ Abschnitte unterteilen. Die $i$-te Kreuzung von Süden nach Norden verbindet den $i$-ten Straßenabschnitt und den $(i + 1)$-ten Straßenabschnitt. Um mögliche Richtungsmehrdeutigkeiten zu vermeiden, sind Kreuzung und Abschnitt Nr. $i$ als Kreuzung und Abschnitt Nr. $i$ von Süden nach Norden definiert.

Jede Kreuzung verfügt über eine Ampel, und aufgrund der Richtungsabhängigkeit der an die Kreuzung angeschlossenen Straßen kann die Zeit, die für das Überqueren derselben Kreuzung bei gleicher Ampelfarbe benötigt wird, in Richtung Norden und Süden unterschiedlich sein. Der Forscher geht davon aus, dass beim zufälligen Überqueren der $i$-ten Kreuzung von Süden nach Norden die Wahrscheinlichkeiten, auf eine rote, gelbe bzw. grüne Ampel zu treffen, $r_i, y_i, g_i$ betragen; beim Überqueren der $i$-ten Kreuzung von Norden nach Süden betragen die Wahrscheinlichkeiten für eine rote, gelbe bzw. grüne Ampel entsprechend $r'_i, y'_i, g'_i$. Es wird angenommen, dass man beim Erreichen der Kreuzung auf genau eine der drei Situationen trifft: Rot, Gelb oder Grün, sodass $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$ gilt.

Um das Problem zu vereinfachen, nimmt der Forscher an, dass unabhängig von Richtung und Zeitpunkt beim Antreffen einer roten, gelben oder grünen Ampel die Wartezeiten immer $1$ Sekunde, $2$ Sekunden bzw. $0$ Sekunden betragen.

Als Teilnehmer am Wettbewerbsprogrammieren hat der Forscher schnell die erwartete Zeit für das Durchqueren des gesamten Straßenabschnitts in beide Richtungen modulo $998\,244\,353$ berechnet. Nun möchte der Forscher jedoch genauere Informationen wissen. Zu diesem Zweck führte er einen Test durch: Vom Startpunkt bis zum Endpunkt zeichnete er die Gesamtwartezeit bis zum Erreichen des $i$-ten Abschnitts auf, bezeichnet als $a_i$; anschließend zeichnete er auf dem Rückweg vom Endpunkt zum Startpunkt die Gesamtwartezeit bis zum Erreichen des $i$-ten Abschnitts auf, bezeichnet als $b_i$. Offensichtlich gilt $a_1 = b_n = 0$ sowie $a_i \le a_{i+1} \le a_i + 2$ und $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Sei $c_i = a_i + b_i$. Der Forscher hat alle $c_i$ ($1 \le i \le n$) aus diesem Test aufgezeichnet.

Der Forscher möchte den praktischen Nutzen dieses Tests ermitteln und hofft daher, für jedes $i = 1, 2, \dots, n$ die Wahrscheinlichkeit zu finden, dass die „Gesamtwartezeit vom Startpunkt bis zum $i$-ten Abschnitt“ + „Gesamtwartezeit vom Endpunkt bis zum $i$-ten Abschnitt“ genau gleich $c_i$ ist, modulo $998\,244\,353$. Da ihn dies vor ein Rätsel stellt, bittet er dich um Hilfe.

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $n$ ($2 \le n \le 2 \times 10^5$).

Die nächsten $n - 1$ Zeilen enthalten jeweils $4$ positive ganze Zahlen. Die $4$ positiven ganzen Zahlen in der $i$-ten Zeile stehen für $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Es wird garantiert, dass diese $4(n - 1)$ positiven ganzen Zahlen $100$ nicht überschreiten und dass sowohl $r_i + y_i$ als auch $r'_i + y'_i$ jeweils $< 1$ sind.

Die nächste Zeile der Eingabe enthält $n$ nichtnegative ganze Zahlen, wobei die $i$-te ganze Zahl $c_i$ ($0 \le c_i \le 2n$) darstellt. Es wird garantiert, dass $a_1, a_2, \dots, a_n$ und $b_1, b_2, \dots, b_n$ existieren, die $a_1 = b_n = 0$ sowie $a_i \le a_{i+1} \le a_i + 2$ und $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) und $a_i + b_i = c_i$ erfüllen.

Ausgabe

Gib eine Zeile mit $n$ nichtnegativen ganzen Zahlen aus. Die $i$-te ganze Zahl repräsentiert die Wahrscheinlichkeit, dass die „Gesamtwartezeit vom Startpunkt bis zum $i$-ten Abschnitt“ + „Gesamtwartezeit vom Endpunkt bis zum $i$-ten Abschnitt“ genau gleich $c_i$ ist, modulo $998\,244\,353$.

Beispiel

Beispiel 1

2
25 25 25 25
0 1

499122177 748683265

Hinweis

Im Beispiel betragen die Wahrscheinlichkeiten, an der $1$-ten Kreuzung in beiden Richtungen auf Rot/Gelb/Grün zu treffen, $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

Hierbei ist die Wahrscheinlichkeit, den $1$-ten Abschnitt von Süden nach Norden mit einer Wartezeit von $a_1 = 0$ zu erreichen, gleich $1$ (da keine Kreuzung überquert wurde), und die Wahrscheinlichkeit, den $1$-ten Abschnitt von Norden nach Süden mit einer Wartezeit von $b_1 = 0$ zu erreichen, ist $\frac{1}{2}$ (d. h. grünes Licht an der $1$-ten Kreuzung), sodass die Wahrscheinlichkeit für $c_1 = 0$ gleich $1 \times \frac{1}{2} = \frac{1}{2}$ ist.

Analog dazu betragen die Wahrscheinlichkeiten, den $2$-ten Abschnitt von Süden nach Norden mit den Wartezeiten $a_2 = 0, 1$ zu erreichen, $\frac{1}{2}, \frac{1}{4}$, und die Wahrscheinlichkeiten, den $2$-ten Abschnitt von Norden nach Süden mit den Wartezeiten $b_2 = 0, 1$ zu erreichen, $1, 0$, sodass die Wahrscheinlichkeit für $c_2 = 1$ gleich $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$ ist.