Descrizione

La strada principale di Mazhen è orientata in direzione nord-sud, partendo dal punto più a sud e terminando nel punto più a nord. Lungo questa strada ci sono $n - 1$ incroci, che dividono l'intera strada in $n$ segmenti. L'$i$-esimo incrocio da sud a nord collega l'$i$-esimo segmento della strada e l'$(i + 1)$-esimo segmento della strada. A causa della potenziale ambiguità nella direzione, l'$i$-esimo incrocio e segmento sono definiti come l'$i$-esimo incrocio e segmento da sud a nord.

Ogni incrocio ha un semaforo e, a causa della natura direzionale delle strade collegate all'incrocio, il tempo impiegato per attraversare lo stesso incrocio con lo stesso colore del semaforo può differire andando verso nord o verso sud. Il ricercatore ritiene che, attraversando casualmente l'$i$-esimo incrocio da sud a nord, le probabilità di incontrare il semaforo rosso, giallo e verde siano rispettivamente $r_i, y_i, g_i$; attraversando l'$i$-esimo incrocio da nord a sud, le probabilità di incontrare il semaforo rosso, giallo e verde siano rispettivamente $r'_i, y'_i, g'_i$. Si assume che, arrivando all'incrocio, si incontrerà una delle tre situazioni: semaforo rosso, giallo o verde, pertanto $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Per semplificare il problema, il ricercatore assume che, indipendentemente dalla direzione e dal momento, quando si incontra un semaforo rosso, giallo o verde, i tempi di attesa siano sempre rispettivamente di $1$ secondo, $2$ secondi e $0$ secondi.

Come partecipante alla programmazione competitiva, il ricercatore ha calcolato rapidamente il tempo atteso per percorrere l'intero tratto stradale in entrambe le direzioni, modulo $998\,244\,353$. Tuttavia, ora il ricercatore vuole conoscere alcune informazioni più specifiche. A tal fine, ha condotto un test: partendo dall'inizio fino alla fine, ha registrato il tempo totale di attesa per raggiungere l'$i$-esimo segmento, indicato con $a_i$; poi, tornando dalla fine all'inizio, ha registrato il tempo totale di attesa per raggiungere l'$i$-esimo segmento, indicato con $b_i$. Chiaramente, $a_1 = b_n = 0$ e $a_i \le a_{i+1} \le a_i + 2$ e $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Sia $c_i = a_i + b_i$. Il ricercatore ha registrato tutti i $c_i$ ($1 \le i \le n$) di questo test.

Il ricercatore vuole conoscere il valore pratico di questo test, quindi spera di trovare la probabilità per ogni $i = 1, 2, \dots, n$ che il «tempo totale di attesa dal punto di partenza all'$i$-esimo segmento» + «tempo totale di attesa dal punto di arrivo all'$i$-esimo segmento» sia esattamente uguale a $c_i$, modulo $998\,244\,353$. Questo problema lo ha messo in difficoltà, quindi si rivolge a te per chiedere aiuto.

Input

La prima riga dell'input contiene un singolo intero $n$ ($2 \le n \le 2 \times 10^5$).

Le successive $n - 1$ righe contengono ciascuna $4$ interi positivi. I $4$ interi positivi dell'$i$-esima riga rappresentano $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. È garantito che questi $4(n - 1)$ interi positivi non superino $100$, e che sia $r_i + y_i$ che $r'_i + y'_i$ siano $< 1$.

La riga successiva dell'input contiene $n$ interi non negativi, dove l'$i$-esimo intero rappresenta $c_i$ ($0 \le c_i \le 2n$). È garantito che esistano $a_1, a_2, \dots, a_n$ e $b_1, b_2, \dots, b_n$ tali che $a_1 = b_n = 0$ e $a_i \le a_{i+1} \le a_i + 2$ e $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) e $a_i + b_i = c_i$.

Output

Stampa una riga con $n$ interi non negativi. L'$i$-esimo intero rappresenta la probabilità che il «tempo totale di attesa dal punto di partenza all'$i$-esimo segmento» + «tempo totale di attesa dal punto di arrivo all'$i$-esimo segmento» sia esattamente uguale a $c_i$, modulo $998\,244\,353$.

Esempio

Esempio 1

2
25 25 25 25
0 1

499122177 748683265

Note

Nell'esempio, le probabilità di incontrare il semaforo rosso/giallo/verde al $1$-o incrocio in entrambe le direzioni sono $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

A questo punto, la probabilità di raggiungere il $1$-o segmento da sud a nord con tempo di attesa $a_1 = 0$ è $1$ (poiché non è stato attraversato alcun incrocio), e la probabilità di raggiungere il $1$-o segmento da nord a sud con tempo di attesa $b_1 = 0$ è $\frac{1}{2}$ (cioè incontrando il semaforo verde al $1$-o incrocio), quindi la probabilità per $c_1 = 0$ è $1 \times \frac{1}{2} = \frac{1}{2}$.

Analogamente, le probabilità di raggiungere il $2$-o segmento da sud a nord con tempi di attesa $a_2 = 0, 1$ sono $\frac{1}{2}, \frac{1}{4}$, e le probabilità di raggiungere il $2$-o segmento da nord a sud con tempi di attesa $b_2 = 0, 1$ sono $1, 0$, quindi la probabilità per $c_2 = 1$ è $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.