Beskrivelse

Hovedveien i Mazhen går i nord-sør-retning, og starter ved det sørligste punktet og slutter ved det nordligste punktet. Langs denne veien er det $n - 1$ veikryss som deler hele veien inn i $n$ segmenter. Det $i$-te veikrysset fra sør til nord forbinder det $i$-te segmentet av veien og det $(i + 1)$-te segmentet av veien. På grunn av mulig tvetydighet i retning defineres det $i$-te veikrysset og segmentet som det $i$-te veikrysset og segmentet fra sør til nord.

Hvert veikryss har et trafikklys, og på grunn av den retningsbestemte naturen til gatene som er koblet til veikrysset, kan tiden det tar å passere gjennom det samme veikrysset med samme lysfarge variere når man kjører nordover og sørover. Forskeren mener at når man tilfeldig passerer gjennom det $i$-te veikrysset fra sør til nord, er sannsynlighetene for å møte rødt lys, gult lys og grønt lys henholdsvis $r_i, y_i, g_i$; når man passerer gjennom det $i$-te veikrysset fra nord til sør, er sannsynlighetene for å møte rødt lys, gult lys og grønt lys henholdsvis $r'_i, y'_i, g'_i$. Det antas at når man kommer til veikrysset, vil man møte én av de tre situasjonene: rødt lys, gult lys eller grønt lys, og dermed er $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

For å forenkle problemet antar forskeren at uavhengig av retning og tidspunkt, når man møter rødt lys, gult lys eller grønt lys, er ventetidene alltid henholdsvis $1$ sekund, $2$ sekunder og $0$ sekunder.

Som deltaker i konkurranseprogrammering regnet forskeren raskt ut forventet tid for å krysse hele veistrekningen i begge retninger modulo $998\,244\,353$. Nå ønsker imidlertid forskeren å vite litt mer spesifikk informasjon. For dette formålet gjennomførte forskeren en test: fra start til slutt registrerte han den totale ventetiden for å nå det $i$-te segmentet, betegnet som $a_i$; deretter, på vei tilbake fra slutt til start, registrerte han den totale ventetiden for å nå det $i$-te segmentet, betegnet som $b_i$. Åpenbart er $a_1 = b_n = 0$ samt $a_i \le a_{i+1} \le a_i + 2$ og $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). La $c_i = a_i + b_i$. Forskeren registrerte alle $c_i$ ($1 \le i \le n$) fra denne testen.

Forskeren ønsker å vite den praktiske verdien av denne testen, så han håper å finne sannsynligheten for hver $i = 1, 2, \dots, n$ for at «total ventetid fra startpunktet til det $i$-te segmentet» + «total ventetid fra sluttpunktet til det $i$-te segmentet» er nøyaktig lik $c_i$, modulo $998\,244\,353$. Dette står han fast på, så han kommer til deg for hjelp.

Inndata

Den første linjen i inndataene inneholder et enkelt heltall $n$ ($2 \le n \le 2 \times 10^5$).

De neste $n - 1$ linjene inneholder hver $4$ positive heltall. De $4$ positive heltallene på den $i$-te linjen representerer $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Det er garantert at disse $4(n - 1)$ positive heltallene ikke overstiger $100$, og at både $r_i + y_i$ og $r'_i + y'_i$ er $< 1$.

Den neste linjen i inndataene inneholder $n$ ikke-negative heltall, der det $i$-te heltallet representerer $c_i$ ($0 \le c_i \le 2n$). Det er garantert at det finnes $a_1, a_2, \dots, a_n$ og $b_1, b_2, \dots, b_n$ som tilfredsstiller $a_1 = b_n = 0$ og $a_i \le a_{i+1} \le a_i + 2$ og $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) samt $a_i + b_i = c_i$.

Utdata

Skriv ut en linje med $n$ ikke-negative heltall. Det $i$-te heltallet representerer sannsynligheten for at «total ventetid fra startpunktet til det $i$-te segmentet» + «total ventetid fra sluttpunktet til det $i$-te segmentet» er nøyaktig lik $c_i$, modulo $998\,244\,353$.

Eksempel

Eksempel 1

2
25 25 25 25
0 1

499122177 748683265

Merk

I eksempelet er sannsynlighetene for å møte rødt/gult/grønt lys ved det $1$-ste veikrysset i begge retninger $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

På dette tidspunktet er sannsynligheten for å nå det $1$-ste segmentet fra sør til nord med ventetid $a_1 = 0$ lik $1$ (siden ingen veikryss ble krysset), og sannsynligheten for å nå det $1$-ste segmentet fra nord til sør med ventetid $b_1 = 0$ er $\frac{1}{2}$ (dvs. grønt lys ved det $1$-ste veikrysset), så sannsynligheten for $c_1 = 0$ er $1 \times \frac{1}{2} = \frac{1}{2}$.

Tilsvarende er sannsynlighetene for å nå det $2$-dre segmentet fra sør til nord med ventetidene $a_2 = 0, 1$ lik $\frac{1}{2}, \frac{1}{4}$, og sannsynlighetene for å nå det $2$-dre segmentet fra nord til sør med ventetidene $b_2 = 0, 1$ er $1, 0$, så sannsynligheten for $c_2 = 1$ er $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.