Kuvaus
Mazhenin päätie kulkee pohjois-eteläsuunnassa alkaen eteläisimmästä pisteestä ja päättyen pohjoisimpaan pisteeseen. Tämän tien varrella on $n - 1$ risteystä, jotka jakavat koko tien $n$ osuuteen. $i$-s risteys etelästä pohjoiseen yhdistää tien $i$-nnen osuuden ja $(i + 1)$-nnen osuuden. Mahdollisen suuntaepäselvyyden vuoksi $i$-s risteys ja osuus määritellään $i$-nneksi risteykseksi ja osuudeksi etelästä pohjoiseen.
Jokaisessa risteyksessä on liikennevalot, ja risteykseen liittyvien katujen suuntaluonteen vuoksi saman risteyksen ylitykseen samalla valon värillä kuluva aika voi poiketa pohjoiseen ja etelään mentäessä. Tutkija uskoo, että kun $i$-s risteys ylitetään satunnaisesti etelästä pohjoiseen, todennäköisyydet kohdata punainen, keltainen ja vihreä valo ovat vastaavasti $r_i, y_i, g_i$; kun taas $i$-s risteys ylitetään pohjoisesta etelään, todennäköisyydet kohdata punainen, keltainen ja vihreä valo ovat vastaavasti $r'_i, y'_i, g'_i$. Oletetaan, että risteykseen saavuttaessa kohdataan jokin näistä kolmesta tilanteesta: punainen valo, keltainen valo tai vihreä valo, joten $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.
Ongelman yksinkertaistamiseksi tutkija olettaa, että suunnasta ja ajasta riippumatta punaisen, keltaisen tai vihreän valon kohdalla odotusajat ovat aina vastaavasti $1$ sekunti, $2$ sekuntia ja $0$ sekuntia.
Kilpaohjelmoijana tutkija laski nopeasti odotusajan koko tieosuuden kulkemiselle molempiin suuntiin modulo $998\,244\,353$. Nyt tutkija haluaa kuitenkin tietää tarkempia tietoja. Tätä varten tutkija suoritti testin: kulkiessaan alusta loppuun hän kirjasi ylös kokonaisodotusajan $i$-nnelle osuudelle saapumiseen, merkittynä $a_i$; palatessaan lopusta alkuun hän kirjasi ylös kokonaisodotusajan $i$-nnelle osuudelle saapumiseen, merkittynä $b_i$. Selvästi $a_1 = b_n = 0$ sekä $a_i \le a_{i+1} \le a_i + 2$ ja $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Olkoon $c_i = a_i + b_i$. Tutkija kirjasi ylös kaikki $c_i$ ($1 \le i \le n$) tästä testistä.
Tutkija haluaa tietää tämän testin käytännön arvon, joten hän toivoo löytävänsä jokaiselle $i = 1, 2, \dots, n$ todennäköisyyden sille, että ”kokonaisodotusaika lähtöpisteestä $i$-nnelle osuudelle” + ”kokonaisodotusaika päätepisteestä $i$-nnelle osuudelle” on täsmälleen $c_i$, modulo $998\,244\,353$. Tämä sai hänet ymmälleen, joten hän kääntyy puoleesi saadakseen apua.
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($2 \le n \le 2 \times 10^5$).
Seuraavat $n - 1$ riviä sisältävät kukin $4$ positiivista kokonaislukua. $i$-nnen rivin $4$ positiivista kokonaislukua esittävät lukuja $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. On taattu, että nämä $4(n - 1)$ positiivista kokonaislukua ovat korkeintaan $100$, ja että sekä $r_i + y_i$ että $r'_i + y'_i$ ovat $< 1$.
Syötteen seuraava rivi sisältää $n$ ei-negatiivista kokonaislukua, missä $i$-s kokonaisluku esittää arvoa $c_i$ ($0 \le c_i \le 2n$). On taattu, että on olemassa $a_1, a_2, \dots, a_n$ ja $b_1, b_2, \dots, b_n$, jotka toteuttavat ehdot $a_1 = b_n = 0$ sekä $a_i \le a_{i+1} \le a_i + 2$ ja $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) sekä $a_i + b_i = c_i$.
Tuloste
Tulosta rivi, jolla on $n$ ei-negatiivista kokonaislukua. $i$-s kokonaisluku esittää todennäköisyyttä sille, että ”kokonaisodotusaika lähtöpisteestä $i$-nnelle osuudelle” + ”kokonaisodotusaika päätepisteestä $i$-nnelle osuudelle” on täsmälleen $c_i$, modulo $998\,244\,353$.
Esimerkki
Esimerkki 1
2
25 25 25 25
0 1499122177 748683265Huomautus
Esimerkissä todennäköisyydet kohdata punainen/keltainen/vihreä valo $1$. risteyksessä molempiin suuntiin ovat $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.
Tällöin todennäköisyys saavuttaa $1$. osuus etelästä pohjoiseen odotusajalla $a_1 = 0$ on $1$ (koska yhtäkään risteystä ei ylitetty), ja todennäköisyys saavuttaa $1$. osuus pohjoisesta etelään odotusajalla $b_1 = 0$ on $\frac{1}{2}$ (eli vihreä valo $1$. risteyksessä), joten todennäköisyys tapaukselle $c_1 = 0$ on $1 \times \frac{1}{2} = \frac{1}{2}$.
Samoin todennäköisyydet saavuttaa $2$. osuus etelästä pohjoiseen odotusajoilla $a_2 = 0, 1$ ovat $\frac{1}{2}, \frac{1}{4}$, ja todennäköisyydet saavuttaa $2$. osuus pohjoisesta etelään odotusajoilla $b_2 = 0, 1$ ovat $1, 0$, joten todennäköisyys tapaukselle $c_2 = 1$ on $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.