題目描述
麻鎮（Mazhen）的主幹道呈南北走向，起點位於最南端，終點位於最北端。沿著這條道路有 $n - 1$ 個交叉路口，將整條道路劃分為 $n$ 個路段。從南到北的第 $i$ 個交叉路口連接了第 $i$ 個路段和第 $(i + 1)$ 個路段。由於方向可能存在歧義，第 $i$ 個交叉路口和路段均定義為從南到北方向的第 $i$ 個交叉路口和路段。
每個交叉路口都設有紅綠燈。由於與交叉路口相連的街道具有方向性，在向北和向南行駛時，以相同顏色的號誌燈通過同一個交叉路口所花費的時間可能會有所不同。研究人員認為，當隨機地從南向北通過第 $i$ 個交叉路口時，遇到紅燈、黃燈和綠燈的機率分別為 $r_i, y_i, g_i$；當從北向南通過第 $i$ 個交叉路口時，遇到紅燈、黃燈和綠燈的機率分別為 $r'_i, y'_i, g'_i$。假設到達交叉路口時，一定會遇到紅燈、黃燈或綠燈這三種情況之一，因此 $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$ 意義下。這難倒了他，所以他來向你求助。
輸入格式
輸入的第一行包含一個整數 $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, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, b_n$ 滿足 $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$。
輸出格式
輸出一行，包含 $n$ 個非負整數。第 $i$ 個整數表示「從起點到第 $i$ 個路段的總等待時間」+「從終點到第 $i$ 個路段的總等待時間」恰好等於 $c_i$ 的機率，在模 $998\,244\,353$ 意義下。
範例
範例 1
2
25 25 25 25
0 1499122177 748683265說明
在範例中，在兩個方向上，在第 $1$ 個交叉路口遇到紅/黃/綠燈的機率均為 $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$。
此時，從南向北到達第 $1$ 個路段且等待時間 $a_1 = 0$ 的機率為 $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}$。