Beskrivning

Huvudvägen i Mazhen går i nord-sydlig riktning, med start vid den sydligaste punkten och slut vid den nordligaste punkten. Längs denna väg finns $n - 1$ korsningar som delar upp hela vägen i $n$ segment. Den $i$-te korsningen från söder till norr förbinder vägens $i$-te segment och vägens $(i + 1)$-te segment. På grund av potentiell tvetydighet i riktning definieras den $i$-te korsningen och segmentet som den $i$-te korsningen och segmentet räknat från söder till norr.

Varje korsning har ett trafikljus, och på grund av den riktade karaktären hos gatorna som är anslutna till korsningen kan tiden det tar att passera samma korsning med samma ljusfärg skilja sig åt när man färdas norrut respektive söderut. Forskaren anser att när man slumpmässigt passerar den $i$-te korsningen från söder till norr är sannolikheterna att möta rött ljus, gult ljus och grönt ljus $r_i, y_i, g_i$ respektive; när man passerar den $i$-te korsningen från norr till söder är sannolikheterna att möta rött ljus, gult ljus och grönt ljus $r'_i, y'_i, g'_i$ respektive. Det antas att man vid ankomsten till korsningen kommer att möta en av de tre situationerna: rött ljus, gult ljus eller grönt ljus, och därmed gäller $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

För att förenkla problemet antar forskaren att oavsett riktning och tidpunkt är väntetiderna vid rött ljus, gult ljus eller grönt ljus alltid $1$ sekund, $2$ sekunder respektive $0$ sekunder.

Som tävlingsprogrammerare beräknade forskaren snabbt den förväntade tiden för att korsa hela vägsträckan i båda riktningarna modulo $998\,244\,353$. Nu vill forskaren dock veta mer specifik information. För detta ändamål genomförde forskaren ett test: från startpunkten till slutpunkten registrerade han den totala väntetiden för att nå det $i$-te segmentet, betecknad som $a_i$; därefter, på vägen tillbaka från slutpunkten till startpunkten, registrerade han den totala väntetiden för att nå det $i$-te segmentet, betecknad som $b_i$. Uppenbarligen gäller $a_1 = b_n = 0$ samt $a_i \le a_{i+1} \le a_i + 2$ och $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Låt $c_i = a_i + b_i$. Forskaren registrerade alla $c_i$ ($1 \le i \le n$) från detta test.

Forskaren vill veta det praktiska värdet av detta test, så han hoppas kunna hitta sannolikheten för varje $i = 1, 2, \dots, n$ att "den totala väntetiden från startpunkten till det $i$-te segmentet" + "den totala väntetiden från slutpunkten till det $i$-te segmentet" är exakt lika med $c_i$, modulo $998\,244\,353$. Detta har satt honom på pottkanten, så han vänder sig till dig för hjälp.

Indata

Den första raden i indatan innehåller ett enda heltal $n$ ($2 \le n \le 2 \times 10^5$).

De följande $n - 1$ raderna innehåller var och en $4$ positiva heltal. De $4$ positiva heltalen på den $i$-te raden representerar $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Det garanteras att dessa $4(n - 1)$ positiva heltal inte överstiger $100$, samt att både $r_i + y_i$ och $r'_i + y'_i$ är $< 1$.

Nästa rad i indatan innehåller $n$ icke-negativa heltal, där det $i$-te heltalet representerar $c_i$ ($0 \le c_i \le 2n$). Det garanteras att det existerar $a_1, a_2, \dots, a_n$ och $b_1, b_2, \dots, b_n$ som uppfyller $a_1 = b_n = 0$ samt $a_i \le a_{i+1} \le a_i + 2$ och $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 rad med $n$ icke-negativa heltal. Det $i$-te heltalet representerar sannolikheten att "den totala väntetiden från startpunkten till det $i$-te segmentet" + "den totala väntetiden från slutpunkten till det $i$-te segmentet" är exakt lika med $c_i$, modulo $998\,244\,353$.

Exempel

Exempel 1

2
25 25 25 25
0 1

499122177 748683265

Anmärkning

I exemplet är sannolikheterna att möta rött/gult/grönt ljus vid den $1$-a korsningen i båda riktningarna $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

Vid denna punkt är sannolikheten att nå det $1$-a segmentet från söder till norr med väntetid $a_1 = 0$ lika med $1$ (eftersom inga korsningar passerades), och sannolikheten att nå det $1$-a segmentet från norr till söder med väntetid $b_1 = 0$ är $\frac{1}{2}$ (dvs. grönt ljus vid den $1$-a korsningen), så sannolikheten för $c_1 = 0$ är $1 \times \frac{1}{2} = \frac{1}{2}$.

På samma sätt är sannolikheterna att nå det $2$-a segmentet från söder till norr med väntetiderna $a_2 = 0, 1$ lika med $\frac{1}{2}, \frac{1}{4}$, och sannolikheterna att nå det $2$-a segmentet från norr till söder med väntetiderna $b_2 = 0, 1$ är $1, 0$, så sannolikheten för $c_2 = 1$ är $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.