Lýsing

Aðalvegurinn í Mazhen liggur í norður-suður átt, byrjar á syðsta punkti og endar á nyrsta punkti. Meðfram þessum vegi eru $n - 1$ gatnamót sem skipta öllum veginum í $n$ kafla. $i$-tu gatnamótin frá suðri til norðurs tengja $i$-ta kafla vegarins og $(i + 1)$-ta kafla vegarins. Vegna mögulegrar tvíræðni í áttum eru $i$-tu gatnamótin og kaflinn skilgreind sem $i$-tu gatnamótin og kaflinn frá suðri til norðurs.

Á hverjum gatnamótum eru umferðarljós og vegna stefnuvirkni gatnanna sem tengjast gatnamótunum getur tíminn sem fer í að fara yfir sömu gatnamót á sama ljósalit verið mismunandi þegar farið er í norður og suður. Rannsakandinn telur að þegar farið er af handahófi yfir $i$-tu gatnamótin frá suðri til norðurs séu líkurnar á að lenda á rauðu ljósi, gulu ljósi og grænu ljósi $r_i, y_i, g_i$, í sömu röð; þegar farið er yfir $i$-tu gatnamótin frá norðri til suðurs séu líkurnar á að lenda á rauðu ljósi, gulu ljósi og grænu ljósi $r'_i, y'_i, g'_i$, í sömu röð. Gert er ráð fyrir að þegar komið er að gatnamótunum muni maður lenda í einni af þessum þremur aðstæðum: rauðu ljósi, gulu ljósi eða grænu ljósi, þannig að $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Til að einfalda verkefnið gerir rannsakandinn ráð fyrir að óháð átt og tíma sé biðtíminn þegar lent er á rauðu ljósi, gulu ljósi eða grænu ljósi alltaf $1$ sekúnda, $2$ sekúndur og $0$ sekúndur, í sömu röð.

Sem keppandi í keppnisforritun reiknaði rannsakandinn fljótt út væntanlegan tíma til að fara yfir allan vegarkaflann í báðar áttir, módúló $998\,244\,353$. Hins vegar vill rannsakandinn nú fá nákvæmari upplýsingar. Í því skyni gerði rannsakandinn prófun: hann fór frá upphafsstað til endastaðar og skráði heildarbiðtímann við að komast á $i$-ta kaflann, táknað sem $a_i$; síðan fór hann til baka frá endastað til upphafsstaðar og skráði heildarbiðtímann við að komast á $i$-ta kaflann, táknað sem $b_i$. Ljóst er að $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$). Látum $c_i = a_i + b_i$. Rannsakandinn skráði öll $c_i$ ($1 \le i \le n$) úr þessari prófun.

Rannsakandinn vill vita hagnýtt gildi þessarar prófunar, svo hann vonast til að finna líkurnar fyrir hvert $i = 1, 2, \dots, n$ á því að „heildarbiðtími frá upphafsstað að $i$-ta kafla“ + „heildarbiðtími frá endastað að $i$-ta kafla“ sé nákvæmlega jafn $c_i$, módúló $998\,244\,353$. Þetta hefur vafist fyrir honum, svo hann leitar til þín eftir aðstoð.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $n$ ($2 \le n \le 2 \times 10^5$).

Næstu $n - 1$ línur innihalda hver um sig $4$ jákvæðar heiltölur. $4$ jákvæðu heiltölurnar í $i$-tu línunni tákna $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Tryggt er að þessar $4(n - 1)$ jákvæðu heiltölur fari ekki yfir $100$, og að bæði $r_i + y_i$ og $r'_i + y'_i$ séu $< 1$.

Næsta lína inntaksins inniheldur $n$ óneikvæðar heiltölur, þar sem $i$-ta heiltalan táknar $c_i$ ($0 \le c_i \le 2n$). Tryggt er að til séu $a_1, a_2, \dots, a_n$ og $b_1, b_2, \dots, b_n$ sem uppfylla $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$) og $a_i + b_i = c_i$.

Úttak

Skrifið út línu með $n$ óneikvæðum heiltölum. $i$-ta heiltalan táknar líkurnar á því að „heildarbiðtími frá upphafsstað að $i$-ta kafla“ + „heildarbiðtími frá endastað að $i$-ta kafla“ sé nákvæmlega jafn $c_i$, módúló $998\,244\,353$.

Dæmi

Dæmi 1

2
25 25 25 25
0 1

499122177 748683265

Athugasemd

Í dæminu eru líkurnar á að lenda á rauðu/gulu/grænu ljósi á $1$. gatnamótunum í báðar áttir $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

Á þessum tímapunkti eru líkurnar á að komast á $1$. kaflann frá suðri til norðurs með biðtíma $a_1 = 0$ jafnar $1$ (þar sem engin gatnamót voru farin), og líkurnar á að komast á $1$. kaflann frá norðri til suðurs með biðtíma $b_1 = 0$ eru $\frac{1}{2}$ (þ.e. grænt ljós á $1$. gatnamótunum), þannig að líkurnar fyrir $c_1 = 0$ eru $1 \times \frac{1}{2} = \frac{1}{2}$.

Á sama hátt eru líkurnar á að komast á $2$. kaflann frá suðri til norðurs með biðtíma $a_2 = 0, 1$ jafnar $\frac{1}{2}, \frac{1}{4}$, og líkurnar á að komast á $2$. kaflann frá norðri til suðurs með biðtíma $b_2 = 0, 1$ eru $1, 0$, þannig að líkurnar fyrir $c_2 = 1$ eru $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.