問題文

麻鎮（Mazhen）の幹線道路は南北方向に伸びており、始点は最南端、終点は最北端にあります。この道路に沿って $n - 1$ 個の交差点があり、道路全体を $n$ 個の区間に分けています。南から北へ $i$ 番目の交差点は、道路の $i$ 番目の区間と $(i + 1)$ 番目の区間を繋いでいます。方向の曖昧さをなくすため、$i$ 番目の交差点および区間は、南から北へ数えて $i$ 番目の交差点および区間として定義されます。

各交差点には信号機があり、交差点に接続する道路の方向性により、同じ色の信号で同じ交差点を通過する場合でも、北向きと南向きでかかる時間が異なる場合があります。研究者は、南から北へ $i$ 番目の交差点をランダムに通過するとき、赤信号、黄信号、青信号に遭遇する確率がそれぞれ $r_i, y_i, g_i$ であり、北から南へ $i$ 番目の交差点を通過するとき、赤信号、黄信号、青信号に遭遇する確率がそれぞれ $r'_i, y'_i, g'_i$ であると考えています。交差点に到着した際、必ず赤信号、黄信号、青信号の3つの状況のいずれかに遭遇するものと仮定するため、$r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$ が成り立ちます。

問題を単純化するため、研究者は進行方向や時間帯にかかわらず、赤信号、黄信号、青信号に遭遇したときの待ち時間は常にそれぞれ $1$ 秒、$2$ 秒、$0$ 秒であると仮定します。

競技プログラミングの参加者である研究者は、道路全体を双方向に通過する期待時間を $998\,244\,353$ を法として素早く計算しました。しかし今、研究者はより具体的な情報を知りたいと考えています。そのために、研究者はあるテストを実施しました。始点から終点へ向かう際に $i$ 番目の区間に到達するまでの合計待ち時間を記録し、それを $a_i$ としました。次に、終点から始点へ戻る際に $i$ 番目の区間に到達するまでの合計待ち時間を記録し、それを $b_i$ としました。明らかに $a_1 = b_n = 0$ であり、かつ $a_i \le a_{i+1} \le a_i + 2$ および $b_{i+1} \le b_i \le b_{i+1} + 2$（$1 \le i < n$）が成り立ちます。$c_i = a_i + b_i$ とおきます。研究者はこのテストにおけるすべての $c_i$（$1 \le i \le n$）を記録しました。

研究者はこのテストの実用的な価値を知りたいため、各 $i = 1, 2, \dots, n$ について、「始点から $i$ 番目の区間までの合計待ち時間」+「終点から $i$ 番目の区間までの合計待ち時間」がちょうど $c_i$ に等しくなる確率を $998\,244\,353$ を法として求めたいと考えています。これには彼も頭を抱えてしまい、あなたに助けを求めました。

入力

入力の1行目には、単一の整数 $n$（$2 \le n \le 2 \times 10^5$）が含まれます。

続く $n - 1$ 行には、それぞれ $4$ 個の正の整数が含まれます。$i$ 行目の $4$ 個の正の整数はそれぞれ $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$ を表します。これら $4(n - 1)$ 個の正の整数はすべて $100$ 以下であり、$r_i + y_i$ と $r'_i + y'_i$ はともに $< 1$ であることが保証されます。

次の行には $n$ 個の非負整数が含まれ、$i$ 番目の整数は $c_i$（$0 \le c_i \le 2n$）を表します。$a_1 = b_n = 0$ かつ $a_i \le a_{i+1} \le a_i + 2$ および $b_{i+1} \le b_i \le b_{i+1} + 2$（$1 \le i < n$）および $a_i + b_i = c_i$ を満たす $a_1, a_2, \dots, a_n$ と $b_1, b_2, \dots, b_n$ が存在することが保証されます。

出力

$n$ 個の非負整数を1行に出力してください。$i$ 番目の整数は、「始点から $i$ 番目の区間までの合計待ち時間」+「終点から $i$ 番目の区間までの合計待ち時間」がちょうど $c_i$ に等しくなる確率を $998\,244\,353$ を法として表したものです。

入出力例

入出力例 1

2
25 25 25 25
0 1

499122177 748683265

注記

例では、双方向ともに $1$ 番目の交差点で赤・黄・青信号に遭遇する確率は $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$ です。

このとき、南から北へ $1$ 番目の区間に待ち時間 $a_1 = 0$ で到達する確率は $1$（交差点を1つも通過していないため）であり、北から南へ $1$ 番目の区間に待ち時間 $b_1 = 0$ で到達する確率は $\frac{1}{2}$（すなわち $1$ 番目の交差点で青信号に遭遇する）であるため、$c_1 = 0$ となる確率は $1 \times \frac{1}{2} = \frac{1}{2}$ となります。

同様に、南から北へ $2$ 番目の区間に待ち時間 $a_2 = 0, 1$ で到達する確率はそれぞれ $\frac{1}{2}, \frac{1}{4}$ であり、北から南へ $2$ 番目の区間に待ち時間 $b_2 = 0, 1$ で到達する確率はそれぞれ $1, 0$ であるため、$c_2 = 1$ となる確率は $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$ となります。