Deskripsi

Jalan utama Mazhen membentang dari utara ke selatan, dimulai dari titik paling selatan dan berakhir di titik paling utara. Di sepanjang jalan ini, terdapat $n - 1$ persimpangan yang membagi seluruh jalan menjadi $n$ segmen. Persimpangan ke-$i$ dari selatan ke utara menghubungkan segmen ke-$i$ dan segmen ke-$(i + 1)$ dari jalan tersebut. Karena potensi ambiguitas arah, persimpangan dan segmen ke-$i$ didefinisikan sebagai persimpangan dan segmen ke-$i$ dari selatan ke utara.

Setiap persimpangan memiliki lampu lalu lintas, dan karena sifat terarah dari jalan-jalan yang terhubung ke persimpangan tersebut, waktu yang dihabiskan untuk melewati persimpangan yang sama dengan warna lampu yang sama dapat berbeda saat menuju ke utara maupun ke selatan. Peneliti meyakini bahwa ketika melewati persimpangan ke-$i$ secara acak dari selatan ke utara, probabilitas menemui lampu merah, lampu kuning, dan lampu hijau masing-masing adalah $r_i, y_i, g_i$; ketika melewati persimpangan ke-$i$ dari utara ke selatan, probabilitas menemui lampu merah, lampu kuning, dan lampu hijau masing-masing adalah $r'_i, y'_i, g'_i$. Diasumsikan bahwa saat tiba di persimpangan, seseorang pasti akan menemui salah satu dari tiga situasi: lampu merah, lampu kuning, atau lampu hijau, sehingga $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Untuk menyederhanakan masalah, peneliti mengasumsikan bahwa terlepas dari arah dan waktu, ketika menemui lampu merah, lampu kuning, atau lampu hijau, waktu tunggunya selalu masing-masing $1$ detik, $2$ detik, dan $0$ detik.

Sebagai peserta pemrograman kompetitif, peneliti dengan cepat menghitung ekspektasi waktu untuk melintasi seluruh segmen jalan di kedua arah dalam modulo $998\,244\,353$. Namun, kini peneliti ingin mengetahui beberapa informasi yang lebih spesifik. Untuk tujuan ini, peneliti melakukan sebuah pengujian: berangkat dari titik awal ke titik akhir, ia mencatat total waktu tunggu untuk mencapai segmen ke-$i$, yang dinyatakan sebagai $a_i$; kemudian, kembali dari titik akhir ke titik awal, ia mencatat total waktu tunggu untuk mencapai segmen ke-$i$, yang dinyatakan sebagai $b_i$. Jelas bahwa $a_1 = b_n = 0$ serta $a_i \le a_{i+1} \le a_i + 2$ dan $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Misalkan $c_i = a_i + b_i$. Peneliti mencatat semua $c_i$ ($1 \le i \le n$) dari pengujian ini.

Peneliti ingin mengetahui nilai praktis dari pengujian ini, sehingga ia berharap dapat menemukan probabilitas untuk setiap $i = 1, 2, \dots, n$ bahwa "total waktu tunggu dari titik awal ke segmen ke-$i$" + "total waktu tunggu dari titik akhir ke segmen ke-$i$" tepat sama dengan $c_i$, dalam modulo $998\,244\,353$. Hal ini membuatnya bingung, sehingga ia datang meminta bantuan Anda.

Masukan

Baris pertama masukan berisi sebuah bilangan bulat $n$ ($2 \le n \le 2 \times 10^5$).

$n - 1$ baris berikutnya masing-masing berisi $4$ bilangan bulat positif. Pada baris ke-$i$, $4$ bilangan bulat positif tersebut masing-masing menyatakan $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Dijamin bahwa $4(n - 1)$ bilangan bulat positif ini tidak melebihi $100$, serta $r_i + y_i$ dan $r'_i + y'_i$ keduanya $< 1$.

Baris masukan berikutnya berisi $n$ bilangan bulat non-negatif, dengan bilangan bulat ke-$i$ menyatakan $c_i$ ($0 \le c_i \le 2n$). Dijamin terdapat $a_1, a_2, \dots, a_n$ dan $b_1, b_2, \dots, b_n$ yang memenuhi $a_1 = b_n = 0$ serta $a_i \le a_{i+1} \le a_i + 2$ dan $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) serta $a_i + b_i = c_i$.

Keluaran

Keluarkan satu baris yang berisi $n$ bilangan bulat non-negatif. Bilangan bulat ke-$i$ menyatakan probabilitas bahwa "total waktu tunggu dari titik awal ke segmen ke-$i$" + "total waktu tunggu dari titik akhir ke segmen ke-$i$" tepat sama dengan $c_i$, dalam modulo $998\,244\,353$.

Contoh

Contoh 1

2
25 25 25 25
0 1

499122177 748683265

Catatan

Pada contoh, probabilitas menemui lampu merah/kuning/hijau di persimpangan ke-$1$ di kedua arah adalah $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

Pada saat ini, probabilitas mencapai segmen ke-$1$ dari selatan ke utara dengan waktu tunggu $a_1 = 0$ adalah $1$ (karena tidak ada persimpangan yang dilewati), dan probabilitas mencapai segmen ke-$1$ dari utara ke selatan dengan waktu tunggu $b_1 = 0$ adalah $\frac{1}{2}$ (yaitu, mendapat lampu hijau di persimpangan ke-$1$), sehingga probabilitas untuk $c_1 = 0$ adalah $1 \times \frac{1}{2} = \frac{1}{2}$.

Demikian pula, probabilitas mencapai segmen ke-$2$ dari selatan ke utara dengan waktu tunggu $a_2 = 0, 1$ adalah $\frac{1}{2}, \frac{1}{4}$, dan probabilitas mencapai segmen ke-$2$ dari utara ke selatan dengan waktu tunggu $b_2 = 0, 1$ adalah $1, 0$, sehingga probabilitas untuk $c_2 = 1$ adalah $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.