Opis

Główna droga w Mazhen biegnie z północy na południe, zaczynając się w najdalej wysuniętym na południe punkcie i kończąc w punkcie najdalej wysuniętym na północ. Wzdłuż tej drogi znajduje się $n - 1$ skrzyżowań, które dzielą całą drogę na $n$ odcinków. $i$-te skrzyżowanie licząc z południa na północ łączy $i$-ty odcinek drogi oraz $(i + 1)$-szy odcinek drogi. Ze względu na możliwą niejednoznaczność kierunku, $i$-te skrzyżowanie i odcinek są definiowane jako $i$-te skrzyżowanie i odcinek licząc z południa na północ.

Na każdym skrzyżowaniu znajduje się sygnalizacja świetlna, a ze względu na kierunkowy charakter ulic połączonych ze skrzyżowaniem czas potrzebny na przejechanie przez to samo skrzyżowanie przy tym samym kolorze światła może się różnić podczas jazdy na północ i na południe. Badacz uważa, że podczas losowego przejazdu przez $i$-te skrzyżowanie z południa na północ prawdopodobieństwa napotkania czerwonego, żółtego i zielonego światła wynoszą odpowiednio $r_i, y_i, g_i$; natomiast podczas przejazdu przez $i$-te skrzyżowanie z północy na południe prawdopodobieństwa napotkania czerwonego, żółtego i zielonego światła wynoszą odpowiednio $r'_i, y'_i, g'_i$. Zakłada się, że po dotarciu do skrzyżowania napotka się jedną z trzech sytuacji: światło czerwone, żółte lub zielone, a zatem $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Aby uprościć problem, badacz zakłada, że niezależnie od kierunku i czasu, po napotkaniu czerwonego, żółtego lub zielonego światła czas oczekiwania wynosi zawsze odpowiednio $1$ sekundę, $2$ sekundy oraz $0$ sekund.

Jako uczestnik zawodów programistycznych badacz szybko obliczył oczekiwany czas pokonania całej drogi w obu kierunkach modulo $998\,244\,353$. Teraz jednak chciałby poznać bardziej szczegółowe informacje. W tym celu przeprowadził test: jadąc od początku do końca, zapisał łączny czas oczekiwania przed dotarciem do $i$-tego odcinka, oznaczony jako $a_i$; następnie, wracając od końca do początku, zapisał łączny czas oczekiwania przed dotarciem do $i$-tego odcinka, oznaczony jako $b_i$. Oczywiście $a_1 = b_n = 0$ oraz $a_i \le a_{i+1} \le a_i + 2$ i $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Niech $c_i = a_i + b_i$. Badacz zapisał wszystkie wartości $c_i$ ($1 \le i \le n$) z tego testu.

Badacz chce poznać praktyczną wartość tego testu, dlatego ma nadzieję znaleźć dla każdego $i = 1, 2, \dots, n$ prawdopodobieństwo, że „łączny czas oczekiwania od punktu początkowego do $i$-tego odcinka” + „łączny czas oczekiwania od punktu końcowego do $i$-tego odcinka” jest dokładnie równy $c_i$, modulo $998\,244\,353$. To zadanie go przerosło, więc zwraca się do Ciebie o pomoc.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($2 \le n \le 2 \times 10^5$).

Kolejne $n - 1$ wierszy zawiera po $4$ dodatnie liczby całkowite. $4$ dodatnie liczby całkowite w $i$-tym wierszu oznaczają odpowiednio $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Gwarantuje się, że te $4(n - 1)$ dodatnie liczby całkowite nie przekraczają $100$, a zarówno $r_i + y_i$, jak i $r'_i + y'_i$ są $< 1$.

Następny wiersz wejścia zawiera $n$ nieujemnych liczb całkowitych, gdzie $i$-ta liczba oznacza $c_i$ ($0 \le c_i \le 2n$). Gwarantuje się, że istnieją ciągi $a_1, a_2, \dots, a_n$ oraz $b_1, b_2, \dots, b_n$ spełniające $a_1 = b_n = 0$ oraz $a_i \le a_{i+1} \le a_i + 2$ i $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) oraz $a_i + b_i = c_i$.

Wyjście

Wypisz jeden wiersz zawierający $n$ nieujemnych liczb całkowitych. $i$-ta liczba całkowita reprezentuje prawdopodobieństwo, że „łączny czas oczekiwania od punktu początkowego do $i$-tego odcinka” + „łączny czas oczekiwania od punktu końcowego do $i$-tego odcinka” jest dokładnie równy $c_i$, modulo $998\,244\,353$.

Przykład

Przykład 1

2
25 25 25 25
0 1

499122177 748683265

Uwaga

W przykładzie prawdopodobieństwa napotkania czerwonego/żółtego/zielonego światła na $1$-szym skrzyżowaniu w obu kierunkach wynoszą $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

Wówczas prawdopodobieństwo dotarcia do $1$-szego odcinka z południa na północ z czasem oczekiwania $a_1 = 0$ wynosi $1$ (ponieważ nie przekroczono żadnego skrzyżowania), a prawdopodobieństwo dotarcia do $1$-szego odcinka z północy na południe z czasem oczekiwania $b_1 = 0$ wynosi $\frac{1}{2}$ (tj. trafienie na zielone światło na $1$-szym skrzyżowaniu), zatem prawdopodobieństwo dla $c_1 = 0$ wynosi $1 \times \frac{1}{2} = \frac{1}{2}$.

Podobnie prawdopodobieństwa dotarcia do $2$-giego odcinka z południa na północ z czasami oczekiwania $a_2 = 0, 1$ wynoszą $\frac{1}{2}, \frac{1}{4}$, a prawdopodobieństwa dotarcia do $2$-giego odcinka z północy na południe z czasami oczekiwania $b_2 = 0, 1$ wynoszą $1, 0$, zatem prawdopodobieństwo dla $c_2 = 1$ wynosi $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.